oj.uz

Submission #730941

# Submission time Handle Problem Language Result Execution time Memory
730941 2023-04-26T16:32:56 Z grogu Passport (JOI23_passport) C++14
16 / 100
 2000 ms 138540 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
ll n,q;
pll a[maxn];
vector<pll> g[maxn];
ll dis[maxn];
ll dis1[maxn];
ll ls[maxn],rs[maxn],tsz = 0,root = 0;
ll id[maxn];
void upd(ll x,ll y,ll w){
    g[x].pb({y,w});
}
void init(ll &v,ll tl,ll tr){
    if(!v) v = ++tsz;
    if(tl==tr){
        id[tl] = v;
        return;
    }
    ll 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(ll v,ll tl,ll tr,ll l,ll r,ll 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(ll poc){
    for(ll i = 1;i<=tsz;i++) dis[i] = llinf;
    dis[poc] = 0;
    priority_queue<pll> pq;
    pq.push({0,poc});
    while(pq.size()){
        pll p = pq.top();
        ll u = p.sc;
        ll cur = -p.fi;
        pq.pop();
        if(cur!=dis[u]) continue;
        for(pll p : g[u]){
            ll s = p.fi;
            ll w = p.sc;
            if(cur+w<dis[s]){
                dis[s] = cur+w;
                pq.push({-dis[s],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 8 ms 12076 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 197 ms 138540 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 6 ms 12104 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12052 KB Output is correct
7 Correct 6 ms 12040 KB Output is correct
8 Correct 8 ms 12112 KB Output is correct
9 Correct 7 ms 12112 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 62 ms 12192 KB Output is correct
12 Correct 39 ms 12180 KB Output is correct
13 Correct 63 ms 12208 KB Output is correct
14 Correct 70 ms 12204 KB Output is correct
15 Correct 20 ms 12116 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12104 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12052 KB Output is correct
7 Correct 6 ms 12040 KB Output is correct
8 Correct 8 ms 12112 KB Output is correct
9 Correct 7 ms 12112 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 62 ms 12192 KB Output is correct
12 Correct 39 ms 12180 KB Output is correct
13 Correct 63 ms 12208 KB Output is correct
14 Correct 70 ms 12204 KB Output is correct
15 Correct 20 ms 12116 KB Output is correct
16 Execution timed out 2057 ms 13048 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12104 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12052 KB Output is correct
7 Correct 6 ms 12040 KB Output is correct
8 Correct 8 ms 12112 KB Output is correct
9 Correct 7 ms 12112 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 62 ms 12192 KB Output is correct
12 Correct 39 ms 12180 KB Output is correct
13 Correct 63 ms 12208 KB Output is correct
14 Correct 70 ms 12204 KB Output is correct
15 Correct 20 ms 12116 KB Output is correct
16 Execution timed out 2057 ms 13048 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12076 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 197 ms 138540 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -