oj.uz

Submission #932949

# Submission time Handle Problem Language Result Execution time Memory
932949 2024-02-24T15:58:07 Z owoovo Passport (JOI23_passport) C++17
6 / 100
 804 ms 235632 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],dis[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],dis,hparg);
    for(int i=1;i<=800000;i++){
        on[i]+=dis[i];
    }
    distra(id[n],dis,hparg);
    for(int i=1;i<=800000;i++){
        on[i]+=dis[i];
    }
    for(int i=1;i<=800000;i++){
        hparg[0].push_back({i,on[i]});
    }
    distra(0,dis,hparg);
    cin>>q;
    for(int i=1;i<=q;i++){
        int v;
        cin>>v;
        if(dis[id[v]]<maxn)cout<<dis[id[v]]<<"\n";
        else cout<<"-1\n";
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 69504 KB Output is correct
2 Correct 30 ms 68812 KB Output is correct
3 Correct 29 ms 69176 KB Output is correct
4 Correct 804 ms 235632 KB Output is correct
5 Correct 384 ms 144568 KB Output is correct
6 Correct 200 ms 124608 KB Output is correct
7 Correct 271 ms 121792 KB Output is correct
8 Correct 190 ms 134816 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70604 KB Output is correct
2 Correct 28 ms 69240 KB Output is correct
3 Correct 28 ms 70092 KB Output is correct
4 Correct 30 ms 69836 KB Output is correct
5 Correct 30 ms 70092 KB Output is correct
6 Correct 31 ms 69180 KB Output is correct
7 Correct 30 ms 70348 KB Output is correct
8 Incorrect 31 ms 68900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70604 KB Output is correct
2 Correct 28 ms 69240 KB Output is correct
3 Correct 28 ms 70092 KB Output is correct
4 Correct 30 ms 69836 KB Output is correct
5 Correct 30 ms 70092 KB Output is correct
6 Correct 31 ms 69180 KB Output is correct
7 Correct 30 ms 70348 KB Output is correct
8 Incorrect 31 ms 68900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70604 KB Output is correct
2 Correct 28 ms 69240 KB Output is correct
3 Correct 28 ms 70092 KB Output is correct
4 Correct 30 ms 69836 KB Output is correct
5 Correct 30 ms 70092 KB Output is correct
6 Correct 31 ms 69180 KB Output is correct
7 Correct 30 ms 70348 KB Output is correct
8 Incorrect 31 ms 68900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 69504 KB Output is correct
2 Correct 30 ms 68812 KB Output is correct
3 Correct 29 ms 69176 KB Output is correct
4 Correct 804 ms 235632 KB Output is correct
5 Correct 384 ms 144568 KB Output is correct
6 Correct 200 ms 124608 KB Output is correct
7 Correct 271 ms 121792 KB Output is correct
8 Correct 190 ms 134816 KB Output is correct
9 Correct 30 ms 70604 KB Output is correct
10 Correct 28 ms 69240 KB Output is correct
11 Correct 28 ms 70092 KB Output is correct
12 Correct 30 ms 69836 KB Output is correct
13 Correct 30 ms 70092 KB Output is correct
14 Correct 31 ms 69180 KB Output is correct
15 Correct 30 ms 70348 KB Output is correct
16 Incorrect 31 ms 68900 KB Output isn't correct
17 Halted 0 ms 0 KB -