oj.uz

Submission #1018116

# Submission time Handle Problem Language Result Execution time Memory
1018116 2024-07-09T14:37:45 Z alexdd Passport (JOI23_passport) C++17
0 / 100
 5 ms 30044 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++)
    {
        rez[id[i]] = dist1[id[i]] + distn[id[i]];
        if(dist1[id[i]] || distn[id[i]]) rez[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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 30040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 30044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 30044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 30044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 30040 KB Output isn't correct
2 Halted 0 ms 0 KB -