Submission #953422

#	Time	Username	Problem	Language	Result	Execution time	Memory
953422		Samot19	Race (IOI11_race)	C++14	0 / 100	2 ms	10588 KiB

race

    #include <bits/stdc++.h>
    using namespace std;
     
    bool remov[200005];
     
    int sz[200005];
     
    int Z;
     
    int res = 1000000000;
     
    vector<pair<int, int>> g[200005];
     
    stack<pair<int, int>> s1;
    stack<int> s2;
     
    int su[1000005]; 
     
    int centroid(int x, int tam, int p=-1) {

        sz[x] = 1;
     
        for(pair<int, int> y : g[x]) {
            if(y.first == p || remov[y.first]) continue;
     
            if(sz[y.first]*2 > tam) return centroid(y.first, tam, x);
        }
     
        return x;
    }
     
    int subtree(int x, int p=-1) {
     
        for(pair<int, int> y : g[x]) {
            if(y.first == p || remov[y.first]) continue;
     
            sz[x] += subtree(y.first, x);
        }
     
        return sz[x];
    }
     
    void dfs(int x, int p, int dist, int cont) {
     
        if(dist > Z) return;
     
        if(dist == Z) {
            res = min(res, cont);
            //cout << x << " " << cont << endl;
            return;
        }
     
        if(su[Z-dist] > 0) {
            res = min(res, su[Z-dist]+cont);
        }
     
        //su[dist] = min(cont, su[dist]);
        s1.push({dist, cont});
        s2.push(dist);
     
        for(pair<int, int> y : g[x]) {
            
            if(y.first == p || remov[y.first]) continue;
     
            dfs(y.first, x, dist+y.second, cont+1);
        }
    }
     
    int xd;
    pair<int, int> lol;
     
    void centdecomp(int x) {
     
        int cent = centroid(x, subtree(x));
     
        for(pair<int, int> y : g[cent]) {
     
            if(remov[y.first]) continue;
     
            while(!s1.empty()) {
     
                lol = s1.top();
                s1.pop();
     
                if(su[lol.first] != 0) {
                    su[lol.first] = min(su[lol.first], lol.second);
                }
                else {
                   su[lol.first] = lol.second;
                }
            }
     
            dfs(y.first, cent, y.second, 1);
            
        }
     
        while(!s2.empty()) {
            xd = s2.top();
            s2.pop();
     
            su[xd] = 0;
        }
     
        remov[cent] = true;
     
        for(pair<int, int> y : g[cent]) {
            if(remov[y.first]) continue;
     
            centdecomp(y.first);
        }
    }
     
    int best_path(int N, int K, int H[][2], int L[]) {
     
        for(int i=0; i<N-1; i++) {
     
            g[H[i][0]].push_back({H[i][1], L[i]});
            g[H[i][1]].push_back({H[i][0], L[i]});
        }
     
        Z = K;
     
        centdecomp(0);
     
        if(res == 1000000000) return -1;
     
        return res;
    }

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57