Submission #1261661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261661		Szymon_Pilipczuk	Passport (JOI23_passport)	C++20	100 / 100	823 ms	105084 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
vector<vector<pair<int,int>>> gr;
pair<int,int> b[200000];
int n;
void add(int l,int r,int p)
{
    p+=n*2;
    l+=n;
    r+=n;
    gr[l].pb({p,0});
    if(l!=r)gr[r].pb({p,0});
    while(l/2 != r/2)
    {
        if(l%2==0)gr[l+1].pb({p,0});
        if(r%2==1)gr[r-1].pb({p,0});
        l/=2;r/=2;
    }
}
int dis[600002][2];
int tdis[600001];
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
void dk(int c,int p,bool m)
{
   // cerr<<c<<" "<<p<<" "<<m<<"\n";  
    for(pair<int,int> i : gr[p])
    {
        //cerr<<i.st<<" "<<i.nd<<"\n";
        if(c + i.nd < dis[i.st][m])
        {
            dis[i.st][m] = c + i.nd;
            pq.push({c+i.nd,i.st,m});
        }   
    }
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq2;
void dk2(int c,int p)
{
    //cerr<<c<<" "<<p<<"\n";
    for(pair<int,int> i : gr[p])
    {
        if(c + i.nd < tdis[i.st])
        {
            tdis[i.st] = c + i.nd;
            pq2.push({c+i.nd,i.st});
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    gr.resize(3*n+2);
    rep(i,n)
    {
        cin>>b[i].st>>b[i].nd;
        b[i].st--;b[i].nd--;
        add(b[i].st,b[i].nd,i);
    }
    gr[n*3].pb({n,0});
    gr[n*3+1].pb({2*n-1,0});
    for(int i = n*2-1;i>1;i--)
    {
        gr[i].pb({i/2,0});
    }
    rep(i,n)
    {
        gr[i+n*2].pb({i+n,1});
    }
    rep(i,n*3+2)
    {
        dis[i][0] = inf;
        dis[i][1] = inf;
    }
    dis[n*3][0] = 0;
    dis[n*3+1][1] = 0;
    pq.push({0,n*3,0});
    pq.push({0,n*3+1,1});
    while(!pq.empty())
    {
        vector<int> cc = pq.top();
        pq.pop();
        if(dis[cc[1]][cc[2]] == cc[0])dk(cc[0],cc[1],cc[2]);
    }
    //cerr<<"\n";
    gr.pop_back();
    gr.pop_back();
    gr.pb({});
    //cerr<<dis[7][0]<<" "<<dis[7][1]<<"\n";
    for(int i = 1;i<3*n;i++)
    {
        gr[n*3].pb({i,dis[i][0] + dis[i][1]});
    }
    rep(i,n*3)
    {
        tdis[i] = inf;
    }
    pq2.push({0,n*3});
    while(!pq2.empty())
    {
        pair<int,int> cc = pq2.top();
        pq2.pop();
        if(tdis[cc.nd] == cc.st)dk2(cc.st,cc.nd);
    }
   // cerr<<tdis[6]<<"\n";
    int q;
    cin>>q;
    rep(i,q)
    {
        int p;
        cin>>p;
        p--;
        if(tdis[p+n] >= inf)
        {
            cout<<-1<<"\n";
        }
        else
        {
            cout<<tdis[p+n]<<"\n";
        }
    }


    
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46