Submission #1004584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004584		anango	Valley (BOI19_valley)	C++17	100 / 100	369 ms	67276 KiB

valley

#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;

int MSB(int x) {
    int t=1;
    int ct=0;
    while (t<=x) {
        t*=2;
        ct++;

    }
    return ct-1;
}

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 = 22;

    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 {
            //binary jump
            int ans = INF;
            int cur = R;
            int tdepth = depth[b];
            int cdepth = depth[R];
            int fdist = dist[R];
            /*for (int p=K-1; p>=0; p--) {
                if (cdepth-(1<<p) >= tdepth) {
                    ans=min(ans,fdist+minima[cur][p]);
                    //cout << "DOING " << p <<" " << cur << " " << fdist+minima[cur][p] << endl;
                    cdepth-=1<<p;
                    cur=multiparent[cur][p];
                }
            }*/
            while (cdepth>tdepth) {
                int lp = MSB(cdepth-tdepth);
                ans=min(ans,fdist+minima[cur][lp]);
                cdepth-=1<<lp;
                cur=multiparent[cur][lp];
            }
            ans=min(ans,fdist+minima[cur][0]);
            if (ans>1LL<<58) {
                cout << "oo" << endl;
            }
            else {
                cout << ans << 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;
    }*/


    
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41