oj.uz

Submission #730943

# Submission time Handle Problem Language Result Execution time Memory
730943 2023-04-26T16:36:03 Z grogu Passport (JOI23_passport) C++14
40 / 100
 2000 ms 129172 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 500005
int n,q;
pair<int,int> a[maxn];
vector<pair<int,ll> > g[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});
}
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);
    upd(v,rs[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);
        return;
    }
    ll mid = (tl+tr)/2;
    upd(ls[v],tl,mid,l,r,u);
    upd(rs[v],mid+1,tr,l,r,u);
}
void getdis(int poc){
    for(int i = 1;i<=tsz;i++) dis[i] = llinf;
    dis[poc] = 0;
    deque<ll> pq;
    pq.pb(poc);
    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);
            }
        }
    }
}
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);
        upd(1,1,n,a[i].fi,a[i].sc,tsz);
    }
    cin >> q;
    while(q--){
        ll x; cin >> x;
        getdis(id[x]);
        for(ll i = 1;i<=tsz;i++) dis1[i] = dis[i];
        ll ans = llinf;
        for(ll i = 1;i<=tsz;i++){
            getdis(i);
            ans = min(ans,dis1[i] + dis[id[1]] + dis[id[n]]);
        }
        if(ans==llinf) ans = -1;
        cout<<ans<<endl;
    }
    return 0;
}
/**
4
1 3
2 4
2 3
4 4
1
1
**/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Runtime error 223 ms 129172 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 12068 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 8 ms 12116 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 19 ms 12076 KB Output is correct
12 Correct 17 ms 12180 KB Output is correct
13 Correct 21 ms 12092 KB Output is correct
14 Correct 20 ms 12196 KB Output is correct
15 Correct 13 ms 12292 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 12068 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 8 ms 12116 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 19 ms 12076 KB Output is correct
12 Correct 17 ms 12180 KB Output is correct
13 Correct 21 ms 12092 KB Output is correct
14 Correct 20 ms 12196 KB Output is correct
15 Correct 13 ms 12292 KB Output is correct
16 Correct 845 ms 12884 KB Output is correct
17 Correct 911 ms 12704 KB Output is correct
18 Correct 1089 ms 13088 KB Output is correct
19 Correct 1010 ms 13056 KB Output is correct
20 Correct 475 ms 12628 KB Output is correct
21 Correct 369 ms 12712 KB Output is correct
22 Correct 297 ms 12572 KB Output is correct
23 Correct 832 ms 12756 KB Output is correct
24 Correct 454 ms 12880 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 12068 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 8 ms 12116 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 19 ms 12076 KB Output is correct
12 Correct 17 ms 12180 KB Output is correct
13 Correct 21 ms 12092 KB Output is correct
14 Correct 20 ms 12196 KB Output is correct
15 Correct 13 ms 12292 KB Output is correct
16 Correct 845 ms 12884 KB Output is correct
17 Correct 911 ms 12704 KB Output is correct
18 Correct 1089 ms 13088 KB Output is correct
19 Correct 1010 ms 13056 KB Output is correct
20 Correct 475 ms 12628 KB Output is correct
21 Correct 369 ms 12712 KB Output is correct
22 Correct 297 ms 12572 KB Output is correct
23 Correct 832 ms 12756 KB Output is correct
24 Correct 454 ms 12880 KB Output is correct
25 Correct 6 ms 11988 KB Output is correct
26 Correct 8 ms 11988 KB Output is correct
27 Execution timed out 2073 ms 12884 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Runtime error 223 ms 129172 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -