oj.uz

Submission #964484

# Submission time Handle Problem Language Result Execution time Memory
964484 2024-04-17T01:26:26 Z irmuun Valley (BOI19_valley) C++17
100 / 100
 173 ms 36916 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=1e5+5;

ll n,s,q,e;
vector<array<ll,3>>adj[N];
vector<pair<ll,ll>>edge;
vector<bool>shop(N,0),path(N,0);
vector<ll>cnt(N,0),d(N,1e18),depth(N),par(N);
ll cur=0;
vector<pair<ll,ll>>que[N];
vector<ll>ans(N,0);

void dfs(ll x,ll p){
    par[x]=p;
    cnt[x]=0;
    if(shop[x]){
        d[x]=0;
        cnt[x]=1;
    }
    for(auto [y,w,i]:adj[x]){
        if(y!=p){
            depth[y]=depth[x]+1;
            dfs(y,x);
            cnt[x]+=cnt[y];
            d[x]=min(d[x],d[y]+w);
        }
    }
};

struct segtree{
    ll n;
    vector<ll>d;
    void set(ll sz){
        n=sz;
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=1e18;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=min(d[node*2],d[node*2+1]);
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 1e18;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=min(d[node*2],d[node*2+1]);
    }
}sg;

void run(ll x,ll p){
    if(d[x]==1e18) sg.update(1,1,N,depth[x],1e18);
    else sg.update(1,1,N,depth[x],d[x]-cur);
    for(auto [I,ind]:que[x]){
        if(path[I]==false){
            ans[ind]=-1;
            continue;
        }
        ll low=edge[I-1].ff;
        if(par[low]!=edge[I-1].ss){
            low=edge[I-1].ss;
        }
        ll D=sg.query(1,1,N,depth[low],depth[x]);
        if(D==1e18){
            ans[ind]=-2;
        }
        else{
            ans[ind]=D+cur;
        }
    }
    for(auto [y,w,j]:adj[x]){
        if(y!=p){
            path[j]=true;
            cur+=w;
            run(y,x);
            path[j]=false;
            cur-=w;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>s>>q>>e;
    for(ll i=1;i<n;i++){//edge
        ll a,b,w;
        cin>>a>>b>>w;
        edge.pb({a,b});
        adj[a].pb({b,w,i});
        adj[b].pb({a,w,i});
    }
    for(ll i=1;i<=s;i++){//shop
        ll c;
        cin>>c;
        shop[c]=true;
    }
    depth[e]=1;
    dfs(e,0);
    sg.set(N);
    for(ll i=1;i<=q;i++){
        ll I,r;
        cin>>I>>r;
        que[r].pb({I,i});
    }
    run(e,0);
    for(ll i=1;i<=q;i++){
        if(ans[i]==-1){
            cout<<"escaped\n";
        }
        else if(ans[i]==-2){
            cout<<"oo\n";
        }
        else{
            cout<<ans[i]<<"\n";
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12400 KB Output is correct
2 Correct 8 ms 12564 KB Output is correct
3 Correct 6 ms 12692 KB Output is correct
4 Correct 6 ms 12652 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12400 KB Output is correct
2 Correct 8 ms 12564 KB Output is correct
3 Correct 6 ms 12692 KB Output is correct
4 Correct 6 ms 12652 KB Output is correct
5 Correct 5 ms 12380 KB Output is correct
6 Correct 7 ms 12380 KB Output is correct
7 Correct 5 ms 12380 KB Output is correct
8 Correct 7 ms 12376 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 5 ms 12380 KB Output is correct
11 Correct 5 ms 12384 KB Output is correct
12 Correct 4 ms 12296 KB Output is correct
13 Correct 7 ms 12380 KB Output is correct
14 Correct 6 ms 12376 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 26716 KB Output is correct
2 Correct 158 ms 27288 KB Output is correct
3 Correct 149 ms 27192 KB Output is correct
4 Correct 151 ms 31016 KB Output is correct
5 Correct 107 ms 31000 KB Output is correct
6 Correct 168 ms 35744 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12400 KB Output is correct
2 Correct 8 ms 12564 KB Output is correct
3 Correct 6 ms 12692 KB Output is correct
4 Correct 6 ms 12652 KB Output is correct
5 Correct 5 ms 12380 KB Output is correct
6 Correct 7 ms 12380 KB Output is correct
7 Correct 5 ms 12380 KB Output is correct
8 Correct 7 ms 12376 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 5 ms 12380 KB Output is correct
11 Correct 5 ms 12384 KB Output is correct
12 Correct 4 ms 12296 KB Output is correct
13 Correct 7 ms 12380 KB Output is correct
14 Correct 6 ms 12376 KB Output is correct
15 Correct 120 ms 26716 KB Output is correct
16 Correct 158 ms 27288 KB Output is correct
17 Correct 149 ms 27192 KB Output is correct
18 Correct 151 ms 31016 KB Output is correct
19 Correct 107 ms 31000 KB Output is correct
20 Correct 168 ms 35744 KB Output is correct
21 Correct 117 ms 26632 KB Output is correct
22 Correct 133 ms 26596 KB Output is correct
23 Correct 130 ms 26828 KB Output is correct
24 Correct 128 ms 30960 KB Output is correct
25 Correct 120 ms 36680 KB Output is correct
26 Correct 111 ms 26808 KB Output is correct
27 Correct 115 ms 26784 KB Output is correct
28 Correct 141 ms 26836 KB Output is correct
29 Correct 173 ms 29516 KB Output is correct
30 Correct 117 ms 32580 KB Output is correct
31 Correct 126 ms 26844 KB Output is correct
32 Correct 114 ms 26732 KB Output is correct
33 Correct 136 ms 26916 KB Output is correct
34 Correct 149 ms 30412 KB Output is correct
35 Correct 159 ms 36916 KB Output is correct
36 Correct 125 ms 30756 KB Output is correct