oj.uz

Submission #730994

# Submission time Handle Problem Language Result Execution time Memory
730994 2023-04-26T18:02:51 Z grogu Passport (JOI23_passport) C++14
100 / 100
 1751 ms 424828 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;

#define maxn 1000005
int n,q;
pair<int,int> a[maxn];
vector<vector<pair<int,ll> > > g(maxn);
vector<vector<pair<int,ll> > > g2(maxn);
ll dis[maxn];
ll dis1[maxn];
int ls[maxn],rs[maxn],tsz = 0,root = 0;
int id[maxn];
void upd(int x,int y,ll w){
    g[x].pb({y,w});
    g2[y].pb({x,w});
}
void upd2(int x,int y,ll w){
    //g2[x].pb({y,w});
}
void init(int &v,int tl,int tr){
    if(!v) v = ++tsz;
    if(tl==tr){
        id[tl] = v;
        return;
    }
    int mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
    upd(v,ls[v],0);
    upd2(ls[v],v,0);
    upd(v,rs[v],0);
    upd2(rs[v],v,0);
}
void upd(int v,int tl,int tr,int l,int r,int u){
    if(l>r||l>tr||tl>r||tl>tr) return;
    if(tl>=l&&tr<=r){
        upd(u,v,0);
        upd2(v,u,1);
        upd2(u,v,0);
        return;
    }
    ll mid = (tl+tr)/2;
    upd(ls[v],tl,mid,l,r,u);
    upd(rs[v],mid+1,tr,l,r,u);
}
bool cmp(ll x,ll y){return dis1[x]<dis1[y];}
void getdis(int poc,bool f,vector<vector<pair<int,ll> > > g){
    deque<ll> pq;
    if(!f){
        for(int i = 1;i<=tsz;i++) dis[i] = llinf;
        dis[poc] = 0;
        pq.pb(poc);
    }else{
        vector<ll> v;
        for(ll i = 1;i<=tsz;i++) if(dis1[i]<llinf) v.pb(i);
        for(ll i = 1;i<=tsz;i++) dis[i] = dis1[i];
        sort(all(v),cmp);
        for(ll x : v) pq.pb(x);
    }
    while(pq.size()){
        ll u = pq.front();
        pq.pop_front();
        for(pll p : g[u]){
            ll s = p.fi;
            ll w = p.sc;
            if(dis[u]+w<dis[s]){
                dis[s] = dis[u]+w;
                if(w) pq.pb(s);
                else pq.push_front(s);
            }
        }
    }
}
ll F[maxn];
int main(){
    ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n;
    init(root,1,n);
    for(ll i = 1;i<=n;i++){
        cin >> a[i].fi >> a[i].sc;
        tsz++;
        upd(id[i],tsz,1);
        upd2(tsz,id[i],0);
        upd(1,1,n,a[i].fi,i-1,tsz);
        upd(1,1,n,i+1,a[i].sc,tsz);
    }
    getdis(id[1],0,g2);
    for(ll i = 1;i<=tsz;i++) dis1[i]+=dis[i];
    getdis(id[n],0,g2);
    for(ll i = 1;i<=tsz;i++) dis1[i]+=dis[i];
    getdis(-1,1,g2);
    cin >> q;
    while(q--){
        ll x; cin >> x;
        ll ans = dis[id[x]];
        if(ans>=llinf) ans = -1;
        cout<<ans<<endl;
    }
    return 0;
}
/**
4
1 3
2 4
2 3
4 4
1
1

5
1 5
2 4
2 3
3 5
1 5
1
3
**/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 70808 KB Output is correct
2 Correct 63 ms 70796 KB Output is correct
3 Correct 61 ms 70856 KB Output is correct
4 Correct 1489 ms 423228 KB Output is correct
5 Correct 758 ms 220336 KB Output is correct
6 Correct 468 ms 177036 KB Output is correct
7 Correct 764 ms 367996 KB Output is correct
8 Correct 720 ms 334232 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 70776 KB Output is correct
2 Correct 80 ms 70820 KB Output is correct
3 Correct 79 ms 70844 KB Output is correct
4 Correct 74 ms 70844 KB Output is correct
5 Correct 60 ms 70820 KB Output is correct
6 Correct 57 ms 70844 KB Output is correct
7 Correct 59 ms 70784 KB Output is correct
8 Correct 77 ms 70868 KB Output is correct
9 Correct 68 ms 70864 KB Output is correct
10 Correct 57 ms 70824 KB Output is correct
11 Correct 61 ms 71000 KB Output is correct
12 Correct 59 ms 70996 KB Output is correct
13 Correct 61 ms 71132 KB Output is correct
14 Correct 59 ms 71124 KB Output is correct
15 Correct 58 ms 70924 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 70776 KB Output is correct
2 Correct 80 ms 70820 KB Output is correct
3 Correct 79 ms 70844 KB Output is correct
4 Correct 74 ms 70844 KB Output is correct
5 Correct 60 ms 70820 KB Output is correct
6 Correct 57 ms 70844 KB Output is correct
7 Correct 59 ms 70784 KB Output is correct
8 Correct 77 ms 70868 KB Output is correct
9 Correct 68 ms 70864 KB Output is correct
10 Correct 57 ms 70824 KB Output is correct
11 Correct 61 ms 71000 KB Output is correct
12 Correct 59 ms 70996 KB Output is correct
13 Correct 61 ms 71132 KB Output is correct
14 Correct 59 ms 71124 KB Output is correct
15 Correct 58 ms 70924 KB Output is correct
16 Correct 69 ms 73392 KB Output is correct
17 Correct 69 ms 72420 KB Output is correct
18 Correct 74 ms 73576 KB Output is correct
19 Correct 66 ms 73476 KB Output is correct
20 Correct 62 ms 72048 KB Output is correct
21 Correct 64 ms 72212 KB Output is correct
22 Correct 71 ms 73368 KB Output is correct
23 Correct 66 ms 73148 KB Output is correct
24 Correct 73 ms 73276 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 70776 KB Output is correct
2 Correct 80 ms 70820 KB Output is correct
3 Correct 79 ms 70844 KB Output is correct
4 Correct 74 ms 70844 KB Output is correct
5 Correct 60 ms 70820 KB Output is correct
6 Correct 57 ms 70844 KB Output is correct
7 Correct 59 ms 70784 KB Output is correct
8 Correct 77 ms 70868 KB Output is correct
9 Correct 68 ms 70864 KB Output is correct
10 Correct 57 ms 70824 KB Output is correct
11 Correct 61 ms 71000 KB Output is correct
12 Correct 59 ms 70996 KB Output is correct
13 Correct 61 ms 71132 KB Output is correct
14 Correct 59 ms 71124 KB Output is correct
15 Correct 58 ms 70924 KB Output is correct
16 Correct 69 ms 73392 KB Output is correct
17 Correct 69 ms 72420 KB Output is correct
18 Correct 74 ms 73576 KB Output is correct
19 Correct 66 ms 73476 KB Output is correct
20 Correct 62 ms 72048 KB Output is correct
21 Correct 64 ms 72212 KB Output is correct
22 Correct 71 ms 73368 KB Output is correct
23 Correct 66 ms 73148 KB Output is correct
24 Correct 73 ms 73276 KB Output is correct
25 Correct 56 ms 70840 KB Output is correct
26 Correct 60 ms 70808 KB Output is correct
27 Correct 67 ms 73528 KB Output is correct
28 Correct 68 ms 72472 KB Output is correct
29 Correct 79 ms 72156 KB Output is correct
30 Correct 64 ms 72252 KB Output is correct
31 Correct 63 ms 72432 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 70808 KB Output is correct
2 Correct 63 ms 70796 KB Output is correct
3 Correct 61 ms 70856 KB Output is correct
4 Correct 1489 ms 423228 KB Output is correct
5 Correct 758 ms 220336 KB Output is correct
6 Correct 468 ms 177036 KB Output is correct
7 Correct 764 ms 367996 KB Output is correct
8 Correct 720 ms 334232 KB Output is correct
9 Correct 76 ms 70776 KB Output is correct
10 Correct 80 ms 70820 KB Output is correct
11 Correct 79 ms 70844 KB Output is correct
12 Correct 74 ms 70844 KB Output is correct
13 Correct 60 ms 70820 KB Output is correct
14 Correct 57 ms 70844 KB Output is correct
15 Correct 59 ms 70784 KB Output is correct
16 Correct 77 ms 70868 KB Output is correct
17 Correct 68 ms 70864 KB Output is correct
18 Correct 57 ms 70824 KB Output is correct
19 Correct 61 ms 71000 KB Output is correct
20 Correct 59 ms 70996 KB Output is correct
21 Correct 61 ms 71132 KB Output is correct
22 Correct 59 ms 71124 KB Output is correct
23 Correct 58 ms 70924 KB Output is correct
24 Correct 69 ms 73392 KB Output is correct
25 Correct 69 ms 72420 KB Output is correct
26 Correct 74 ms 73576 KB Output is correct
27 Correct 66 ms 73476 KB Output is correct
28 Correct 62 ms 72048 KB Output is correct
29 Correct 64 ms 72212 KB Output is correct
30 Correct 71 ms 73368 KB Output is correct
31 Correct 66 ms 73148 KB Output is correct
32 Correct 73 ms 73276 KB Output is correct
33 Correct 56 ms 70840 KB Output is correct
34 Correct 60 ms 70808 KB Output is correct
35 Correct 67 ms 73528 KB Output is correct
36 Correct 68 ms 72472 KB Output is correct
37 Correct 79 ms 72156 KB Output is correct
38 Correct 64 ms 72252 KB Output is correct
39 Correct 63 ms 72432 KB Output is correct
40 Correct 1751 ms 424828 KB Output is correct
41 Correct 768 ms 222644 KB Output is correct
42 Correct 1006 ms 371644 KB Output is correct
43 Correct 975 ms 363892 KB Output is correct
44 Correct 488 ms 178376 KB Output is correct
45 Correct 639 ms 201708 KB Output is correct
46 Correct 306 ms 120988 KB Output is correct
47 Correct 928 ms 307948 KB Output is correct
48 Correct 960 ms 333380 KB Output is correct