oj.uz

Submission #932953

# Submission time Handle Problem Language Result Execution time Memory
932953 2024-02-24T16:08:12 Z owoovo Passport (JOI23_passport) C++14
0 / 100
 784 ms 213452 KB 
#include<bits/stdc++.h>
#define F first 
#define S second 
#define int long long
using namespace std;
const int maxn=1e17;
vector<pair<int,int>> graph[800010],hparg[800010];
int n,q,cnt,id[200010],on[800010],dis1[800010],dis2[800010];
void build(int l,int r,int now){
    if(l==r){
        id[l]=now;
        return;
    }
    int m=(l+r)>>1;
    graph[now].push_back({now*2,0});
    graph[now].push_back({now*2+1,0});
    build(l,m,now*2);
    build(m+1,r,now*2+1);
    return;
}
void pls(int l,int r,int tl,int tr,int nid,int uid){
    if(tl==l&&r==tr){
        graph[uid].push_back({nid,1});
        return;
    }
    int m=(l+r)>>1;
    if(tr<=m)pls(l,m,tl,tr,nid*2,uid);
    else if(m+1<=tl)pls(m+1,r,tl,tr,nid*2+1,uid);
    else{
        pls(l,m,tl,m,nid*2,uid);
        pls(m+1,r,m+1,tr,nid*2+1,uid);
    }
    return;
}
void distra(int s,int* dis,vector<pair<int,int>>* graph){
    priority_queue< pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>> > pq;
    for(int i=0;i<=800000;i++)*(dis+i)=maxn;
    (*(dis+s))=0;
    pq.push({0ll,s});
    while(!pq.empty()){
        auto [d,v]=pq.top();
        pq.pop();
        if(d>(*(dis+v)))continue;
        for(auto &[ne,w]:(*(graph+v))){
            if((*(dis+ne))>w+d){
                (*(dis+ne))=w+d;
                pq.push({w+d,ne});
            }    
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    build(1,n,1);
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        pls(1,n,l,r,1,id[i]);
    }
    for(int i=1;i<=800000;i++){
        for(auto &[v,w]:graph[i]){
            hparg[v].push_back({i,w});
        }
    }

    distra(id[1],dis1,hparg);
    distra(id[n],dis2,hparg);

    for(int i=1;i<=n;i++)hparg[0].push_back({i,max(0ll,dis1[i]-1)+max(0ll,dis2[i]-1)+1});

    distra(0,dis1,hparg);
    cin>>q;
    for(int i=1;i<=q;i++){
        int v;
        cin>>v;
        if(dis1[id[v]]<maxn)cout<<dis1[id[v]]<<"\n";
        else cout<<"-1\n";
    }
    return 0;
}

Compilation message

passport.cpp: In function 'void distra(long long int, long long int*, std::vector<std::pair<long long int, long long int> >*)':
passport.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         auto [d,v]=pq.top();
      |              ^
passport.cpp:44:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         for(auto &[ne,w]:(*(graph+v))){
      |                   ^
passport.cpp: In function 'int main()':
passport.cpp:64:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         for(auto &[v,w]:graph[i]){
      |                   ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 54104 KB Output is correct
2 Correct 14 ms 54108 KB Output is correct
3 Correct 15 ms 54108 KB Output is correct
4 Correct 784 ms 213452 KB Output is correct
5 Correct 339 ms 124352 KB Output is correct
6 Correct 190 ms 104404 KB Output is correct
7 Incorrect 213 ms 102616 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 54280 KB Output is correct
2 Correct 14 ms 54360 KB Output is correct
3 Correct 14 ms 54108 KB Output is correct
4 Correct 14 ms 54108 KB Output is correct
5 Incorrect 14 ms 54376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 54280 KB Output is correct
2 Correct 14 ms 54360 KB Output is correct
3 Correct 14 ms 54108 KB Output is correct
4 Correct 14 ms 54108 KB Output is correct
5 Incorrect 14 ms 54376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 54280 KB Output is correct
2 Correct 14 ms 54360 KB Output is correct
3 Correct 14 ms 54108 KB Output is correct
4 Correct 14 ms 54108 KB Output is correct
5 Incorrect 14 ms 54376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 54104 KB Output is correct
2 Correct 14 ms 54108 KB Output is correct
3 Correct 15 ms 54108 KB Output is correct
4 Correct 784 ms 213452 KB Output is correct
5 Correct 339 ms 124352 KB Output is correct
6 Correct 190 ms 104404 KB Output is correct
7 Incorrect 213 ms 102616 KB Output isn't correct
8 Halted 0 ms 0 KB -