oj.uz

Submission #730944

# Submission time Handle Problem Language Result Execution time Memory
730944 2023-04-26T16:40:36 Z grogu Passport (JOI23_passport) C++14
48 / 100
 1480 ms 471964 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 10005
int n,q;
pair<int,int> a[maxn];
vector<pair<int,ll> > g[maxn];
ll dis[maxn][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[poc][i] = llinf;
    dis[poc][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[poc][u]+w<dis[poc][s]){
                dis[poc][s] = dis[poc][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);
        upd(1,1,n,a[i].fi,a[i].sc,tsz);
    }
    for(ll i = 1;i<=tsz;i++) getdis(i);
    for(ll i = 1;i<=tsz;i++) F[i] = -2;
    cin >> q;
    while(q--){
        ll x; cin >> x;
        if(F[x]!=-2){
            cout<<F[x]<<endl;
            continue;
        }
        ll ans = llinf;
        for(ll i = 1;i<=tsz;i++){
            ans = min(ans,dis[id[x]][i] + dis[i][id[1]] + dis[i][id[n]]);
        }
        if(ans==llinf) ans = -1;
        F[x] = ans;
        cout<<F[x]<<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 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 34 ms 10832 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 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 15 ms 9812 KB Output is correct
12 Correct 17 ms 10368 KB Output is correct
13 Correct 25 ms 10616 KB Output is correct
14 Correct 19 ms 9908 KB Output is correct
15 Correct 10 ms 10580 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 15 ms 9812 KB Output is correct
12 Correct 17 ms 10368 KB Output is correct
13 Correct 25 ms 10616 KB Output is correct
14 Correct 19 ms 9908 KB Output is correct
15 Correct 10 ms 10580 KB Output is correct
16 Correct 1071 ms 414156 KB Output is correct
17 Correct 1185 ms 466420 KB Output is correct
18 Correct 1351 ms 471964 KB Output is correct
19 Correct 1251 ms 447784 KB Output is correct
20 Correct 652 ms 471480 KB Output is correct
21 Correct 568 ms 471544 KB Output is correct
22 Correct 468 ms 471360 KB Output is correct
23 Correct 1000 ms 471504 KB Output is correct
24 Correct 611 ms 471652 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 15 ms 9812 KB Output is correct
12 Correct 17 ms 10368 KB Output is correct
13 Correct 25 ms 10616 KB Output is correct
14 Correct 19 ms 9908 KB Output is correct
15 Correct 10 ms 10580 KB Output is correct
16 Correct 1071 ms 414156 KB Output is correct
17 Correct 1185 ms 466420 KB Output is correct
18 Correct 1351 ms 471964 KB Output is correct
19 Correct 1251 ms 447784 KB Output is correct
20 Correct 652 ms 471480 KB Output is correct
21 Correct 568 ms 471544 KB Output is correct
22 Correct 468 ms 471360 KB Output is correct
23 Correct 1000 ms 471504 KB Output is correct
24 Correct 611 ms 471652 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 0 ms 596 KB Output is correct
27 Correct 1468 ms 442696 KB Output is correct
28 Correct 1480 ms 471676 KB Output is correct
29 Correct 1052 ms 471480 KB Output is correct
30 Correct 917 ms 471500 KB Output is correct
31 Correct 1225 ms 443820 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 34 ms 10832 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -