oj.uz

Submission #1018197

# Submission time Handle Problem Language Result Execution time Memory
1018197 2024-07-09T16:09:39 Z alexdd Passport (JOI23_passport) C++17
6 / 100
 580 ms 119676 KB 
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n,cntn;
vector<pair<int,int>> con[530005];
vector<pair<int,int>> conrev[530005];
int id[200005];
void build(int nod, int st, int dr)
{
    cntn = max(cntn, nod);
    if(st==dr)
    {
        id[st]=nod;
        return;
    }
    con[nod].push_back({nod*2,0});
    con[nod].push_back({nod*2+1,0});
    conrev[nod*2].push_back({nod,0});
    conrev[nod*2+1].push_back({nod,0});
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void baga(int nod, int st, int dr, int le, int ri, int from)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        con[from].push_back({nod,1});
        conrev[nod].push_back({from,1});
        return;
    }
    int mij=(st+dr)/2;
    baga(nod*2,st,mij,le,min(mij,ri),from);
    baga(nod*2+1,mij+1,dr,max(mij+1,le),ri,from);
}
void bfs(int src, int dist[])
{
    for(int i=1;i<=cntn;i++)
        dist[i]=INF;
    deque<int> dq;
    dist[src]=0;
    dq.push_back(src);
    while(!dq.empty())
    {
        int nod = dq.front();
        dq.pop_front();
        for(auto [adj,c]:conrev[nod])
        {
            if(dist[adj] > dist[nod]+c)
            {
                dist[adj] = dist[nod]+c;
                if(c==1) dq.push_back(adj);
                else dq.push_front(adj);
            }
        }
    }
}
int dist1[530000],distn[530000],rez[530000];
void dijkstra()
{
    for(int i=1;i<=cntn;i++)
        rez[i]=INF;
    priority_queue<pair<int,int>> pq;
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            rez[id[i]] = distn[id[i]];
        }
        else if(i==n)
        {
            rez[id[i]] = dist1[id[i]];
        }
        else if(dist1[id[i]]==1 && distn[id[i]]==1)
        {
            rez[id[i]] = 1;
        }
        else if(dist1[id[i]]==1)
        {
            rez[id[i]] = distn[id[i]];
        }
        else if(distn[id[i]]==1)
        {
            rez[id[i]] = dist1[id[i]];
        }
        else
        {
            rez[id[i]] = dist1[id[i]] + distn[id[i]];
        }
        pq.push({-rez[id[i]],id[i]});
    }
    while(!pq.empty())
    {
        int nod = pq.top().second;
        int cdist = -pq.top().first;
        pq.pop();
        if(rez[nod]!=cdist)
            continue;
        for(auto [adj,c]:conrev[nod])
        {
            if(rez[adj]>rez[nod]+c)
            {
                rez[adj] = rez[nod]+c;
                pq.push({-rez[adj],adj});
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    build(1,1,n);
    int le,ri;
    for(int i=1;i<=n;i++)
    {
        cin>>le>>ri;
        baga(1,1,n,le,ri,id[i]);
    }
    bfs(id[1],dist1);
    bfs(id[n],distn);
    //for(int i=1;i<=n;i++) cout<<i<<"  "<<dist1[id[i]]<<" "<<distn[id[i]]<<"  dist1 & distn\n";
    dijkstra();
    int q,a;
    cin>>q;
    while(q--)
    {
        cin>>a;
        if(rez[id[a]]<=n+5) cout<<rez[id[a]]<<"\n";
        else cout<<-1<<"\n";
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25180 KB Output is correct
2 Correct 9 ms 25180 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 580 ms 119676 KB Output is correct
5 Correct 369 ms 76744 KB Output is correct
6 Correct 184 ms 64076 KB Output is correct
7 Correct 125 ms 62916 KB Output is correct
8 Correct 125 ms 76296 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25380 KB Output is correct
2 Correct 10 ms 25272 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 11 ms 25324 KB Output is correct
5 Correct 10 ms 25360 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 13 ms 25180 KB Output is correct
9 Correct 10 ms 25180 KB Output is correct
10 Correct 10 ms 25180 KB Output is correct
11 Correct 9 ms 25384 KB Output is correct
12 Incorrect 10 ms 25432 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25380 KB Output is correct
2 Correct 10 ms 25272 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 11 ms 25324 KB Output is correct
5 Correct 10 ms 25360 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 13 ms 25180 KB Output is correct
9 Correct 10 ms 25180 KB Output is correct
10 Correct 10 ms 25180 KB Output is correct
11 Correct 9 ms 25384 KB Output is correct
12 Incorrect 10 ms 25432 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25380 KB Output is correct
2 Correct 10 ms 25272 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 11 ms 25324 KB Output is correct
5 Correct 10 ms 25360 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 13 ms 25180 KB Output is correct
9 Correct 10 ms 25180 KB Output is correct
10 Correct 10 ms 25180 KB Output is correct
11 Correct 9 ms 25384 KB Output is correct
12 Incorrect 10 ms 25432 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25180 KB Output is correct
2 Correct 9 ms 25180 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 580 ms 119676 KB Output is correct
5 Correct 369 ms 76744 KB Output is correct
6 Correct 184 ms 64076 KB Output is correct
7 Correct 125 ms 62916 KB Output is correct
8 Correct 125 ms 76296 KB Output is correct
9 Correct 10 ms 25380 KB Output is correct
10 Correct 10 ms 25272 KB Output is correct
11 Correct 10 ms 25180 KB Output is correct
12 Correct 11 ms 25324 KB Output is correct
13 Correct 10 ms 25360 KB Output is correct
14 Correct 10 ms 25180 KB Output is correct
15 Correct 10 ms 25180 KB Output is correct
16 Correct 13 ms 25180 KB Output is correct
17 Correct 10 ms 25180 KB Output is correct
18 Correct 10 ms 25180 KB Output is correct
19 Correct 9 ms 25384 KB Output is correct
20 Incorrect 10 ms 25432 KB Output isn't correct
21 Halted 0 ms 0 KB -