oj.uz

Submission #633172

# Submission time Handle Problem Language Result Execution time Memory
633172 2022-08-21T18:14:31 Z Iwanttobreakfree Valley (BOI19_valley) C++17
59 / 100
 557 ms 39496 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define int long long
#define pii pair<int,int>
int logn=18;
struct CELL{
    int node,w,id;
};
int t=0;
bool is_ancestor(int a,int b,vector<pii>& time){
    if(time[a].first<time[b].first&&time[a].second>time[b].second)return true;
    return false;
}
int get_par(int a,int x,vector<vector<int>>& par){
    for(int i=logn-1;i>=0;i--){
        if(x&(1<<i))a=par[a][i];
    }
    return a;
}
bool escape(int anc,int x,vector<vector<int>>& p,vector<int>& depth,vector<pii>& time){
    int dif=depth[x]-depth[anc];
    if(get_par(x,dif,p)==anc)return false;
    return true;
}
void dfs(int a,int par,vector<vector<CELL>>& g,vector<pii>& time,vector<vector<int>>& p,vector<int>& depth){
    time[a].first=t;
    t++;
    p[a][0]=par;
    depth[a]=depth[par]+1;
    for(int j=1;j<logn;j++){
        p[a][j]=p[p[a][j-1]][j-1];
    }
    for(auto v:g[a]){
        if(par==v.node)continue;
        dfs(v.node,a,g,time,p,depth);
    }
    time[a].second=t;
    t++;
}
int dijkstra(int a,int i,vector<vector<CELL>>& g,vector<int>& shop){
    priority_queue<pii> pq;
    pq.push({0,a});
    int n=g.size();
    vector<int> dist(n,1e18);
    dist[a]=0;
    while(!pq.empty()){
        int u=pq.top().second,d=-pq.top().first;
        pq.pop();
        if(dist[u]<d)continue;
        for(auto v:g[u]){
            if(v.id==i)continue;
            if(dist[v.node]>dist[u]+v.w){
                dist[v.node]=dist[u]+v.w;
                pq.push({-dist[v.node],v.node});
            }
        }
    }
    int ans=1e18;
    for(int s:shop){
        ans=min(ans,dist[s]);
    }
    return ans;
}
signed main(){
    int n,s,q,e,x,y,w;
    cin>>n>>s>>q>>e;
    e--;
    vector<pii> edges(n-1),time(n);
    vector<vector<CELL>> g(n,vector<CELL>());
    vector<vector<int>> p(n,vector<int>(logn));
    vector<int> shop(s),depth(n);
    for(int i=0;i<n-1;i++){
        cin>>x>>y>>w;
        x--;y--;
        g[x].push_back({y,w,i});
        g[y].push_back({x,w,i});
        edges[i]={x,y};
    }
    for(int i=0;i<s;i++){
        cin>>shop[i];
        shop[i]--;
    }
    dfs(e,e,g,time,p,depth);
    //for(int i=0;i<n;i++)cout<<depth[i]<<' ';
    while(q--){
        cin>>x>>y;
        x--;y--;
        int anc=edges[x].first;
        if(time[edges[x].second]>time[anc])anc=edges[x].second;
        //cout<<anc<<'\n';
        if(escape(anc,y,p,depth,time))cout<<"escaped\n";
        else{
            if(n*q>1e6){
                cout<<"0\n";
            }else{
                int ans=dijkstra(y,x,g,shop);
                if(ans==1e18)cout<<"oo\n";
                else cout<<ans<<'\n';
            }
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 440 KB Output is correct
2 Correct 20 ms 468 KB Output is correct
3 Correct 21 ms 340 KB Output is correct
4 Correct 20 ms 440 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 440 KB Output is correct
2 Correct 20 ms 468 KB Output is correct
3 Correct 21 ms 340 KB Output is correct
4 Correct 20 ms 440 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 6 ms 564 KB Output is correct
8 Correct 4 ms 608 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 15 ms 656 KB Output is correct
11 Correct 5 ms 568 KB Output is correct
12 Correct 6 ms 596 KB Output is correct
13 Correct 7 ms 596 KB Output is correct
14 Correct 20 ms 568 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 34316 KB Output is correct
2 Correct 395 ms 34308 KB Output is correct
3 Correct 405 ms 34764 KB Output is correct
4 Correct 530 ms 37000 KB Output is correct
5 Correct 434 ms 36124 KB Output is correct
6 Correct 557 ms 39496 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 440 KB Output is correct
2 Correct 20 ms 468 KB Output is correct
3 Correct 21 ms 340 KB Output is correct
4 Correct 20 ms 440 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 6 ms 564 KB Output is correct
8 Correct 4 ms 608 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 15 ms 656 KB Output is correct
11 Correct 5 ms 568 KB Output is correct
12 Correct 6 ms 596 KB Output is correct
13 Correct 7 ms 596 KB Output is correct
14 Correct 20 ms 568 KB Output is correct
15 Correct 384 ms 34316 KB Output is correct
16 Correct 395 ms 34308 KB Output is correct
17 Correct 405 ms 34764 KB Output is correct
18 Correct 530 ms 37000 KB Output is correct
19 Correct 434 ms 36124 KB Output is correct
20 Correct 557 ms 39496 KB Output is correct
21 Incorrect 397 ms 33552 KB Output isn't correct
22 Halted 0 ms 0 KB -