Submission #1004448

#TimeUsernameProblemLanguageResultExecution timeMemory
1004448anangoValley (BOI19_valley)C++17
23 / 100
312 ms35012 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,s,q,e;
int INF = 1LL<<60;
vector<vector<pair<int,int>>> adjlist;
vector<int> dist;
vector<int> dp1;
vector<int> is_shop;
vector<int> parent;
vector<int> depth;
vector<int> blubber;
vector<int> preorder, postorder;
int current = 0;

void dfs(int node, int par) {
    //cout << node <<" " << par << endl;
    preorder[node] = current;
    current++;
    for (auto j:adjlist[node]) {
        int w = j.second;
        int x = j.first;
        if (x!=par) {
            dist[x] = min(dist[x], dist[node]+w);
            depth[x] = depth[node]+1;
            parent[x] = node;
            dfs(x,node);
            dp1[node] = min(dp1[node],dp1[x]+w);
        }
    }
    postorder[node] = current;
    current++;
}


signed main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
    /*#ifdef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif*/ //fast IO 
    cin >> n >> s >> q >> e;
    e--;
    adjlist=vector<vector<pair<int,int>>>(n);
    dist=dp1=blubber=vector<int>(n,INF);
    is_shop = depth = vector<int>(n,0);
    preorder = postorder = parent = vector<int>(n,-1);
    vector<pair<int,int>> edges;
    for (int i=0; i<n-1; i++) {
        int a,b,w;
        cin >> a >> b >> w;
        a--;
        b--;
        //cout << a <<" " << b <<" " << w << " " << adjlist.size() << endl;
        adjlist[a].push_back({b,w});
        adjlist[b].push_back({a,w});
        edges.push_back({a,b});
    }
    for (int i=0; i<s; i++) {
        int x;
        cin >> x;
        x--;
        is_shop[x] = 1;
        dp1[x] = 0;
    }
    dist[e] = 0;
    dfs(e,-1);
    for (int i=0; i<n; i++) {
        if (dp1[i]==INF) {
            blubber[i] = INF;
        }
        else {
            blubber[i] = dp1[i]-dist[i];
        }
    }
    int K = 3;

    vector<vector<int>> multiparent(n,vector<int>(K,-1));
    vector<vector<int>> minima(n,vector<int>(K,INF)); //min value of blubber upto 2^j ancestors
    for (int i=0; i<n; i++) {
        multiparent[i][0] = parent[i];
        minima[i][0] = blubber[i];
    }
    parent[e] = multiparent[e][0] = e;
    cout << endl;
    for (int p=1; p<K; p++) {
        for (int i=0; i<n; i++) {
            //cout << i <<" " << p << " " << multiparent[i][p-1] << endl;
            multiparent[i][p] = multiparent[multiparent[i][p-1]][p-1];
            minima[i][p] = min(minima[i][p-1], minima[multiparent[i][p-1]][p-1]);
        }
    }
    for (int qu=0; qu<q; qu++) {
        int I,R;
        cin >> I >> R;
        I--;
        R--;
        int a = edges[I].first;
        int b = edges[I].second;
        if (depth[a]>depth[b]) {
            swap(a,b);
        }
        //care about b (higher depth)
        //if R is not in the subtree of b then it's escaped
        //cout << b <<" " << R<<" " << preorder[b] <<" " << preorder[R] << " " << postorder[R] << " " << postorder[b] << endl;
        if (!(preorder[b]<=preorder[R] && preorder[R]<=postorder[R] && postorder[R]<=postorder[b])) {
            cout << "escaped" << endl;
        }
        else {
            cout << 0 << endl;
        }


    }

    for (int i=0; i<n; i++) {
        //cout << i <<" " << preorder[i] <<" " << postorder[i] << endl;
    }
    /*for (int p=0; p<K; p++) {
        cout << "lifting " << p << endl;
        for (int i=0; i<n; i++) {
            cout << i <<" " << multiparent[i][p] <<" " << minima[i][p] << endl;
        }
    }



    cout << "blubbers" << endl;
    for (int i=0; i<n; i++) {
        cout << i << " " << dist[i] << " " << dp1[i] << " " << blubber[i] << endl;
    }*/


    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...