Submission #242187

#	Time	Username	Problem	Language	Result	Execution time	Memory
242187		oolimry	Valley (BOI19_valley)	C++14	100 / 100	957 ms	144924 KiB

valley

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long,long long> ii;
static vector<ii> adj[100005];
static long long dis[100005];
static long long depth[100005];
static long long vis[100005];
static long long sz[100005];
static long long cented[100005];
static vector<ii> parent[100005];
static vector<long long> nodes;

static vector<ii> disc[100005];
static vector<int> disc2[100005];

static long long low[100005];
static long long high[100005];
int cnt = 0;
long long n, q, S, E;

void dfs(int u){
    sz[u] = 1;
    nodes.push_back(u);
    for(ii v : adj[u]){
        if(sz[v.first] == 0 && !cented[v.first]){
            dis[v.first] = dis[u] + v.second;
            dfs(v.first);
            sz[u] += sz[v.first];

        }
    }
}

void dfs2(int u){
    low[u] = cnt;
    high[u] = cnt;
    cnt++;
    vis[u] = true;
    for(ii v : adj[u]){
        if(!vis[v.first]){
            depth[v.first] = depth[u] + 1;
            dfs2(v.first);
            high[u] = max(high[u],high[v.first]);
        }
    }
}


void recurse(int r, int p){
    nodes.clear();
    dfs(r);
    int centroid;
    for(int u : nodes){
        long long big = sz[r] - sz[u];
        for(ii v : adj[u]){
            if(!cented[v.first] && sz[v.first] < sz[u]){
                big = max(big, sz[v.first]);
            }
        }
        if(2*big <= sz[r]){
            centroid = u;
            break;
        }
    }

    for(int u : nodes){
        sz[u] = 0;
        if(p != -1) parent[u].push_back(ii(p,dis[u]));
        dis[u] = 0;
    }
    cented[centroid] = true;
    for(ii v : adj[centroid]){
        dis[v.first] = v.second;
        if(!cented[v.first]) recurse(v.first, centroid);
    }
}

struct edge{
    long long u;
    long long v;
    long long w;
};

class SegmentTree{
public:
    int nn;
    vector<long long> tree;

    void create(int nnn){
        nn = nnn;
        for(int i = 0;i < 2*nn+4;i++){
            tree.push_back(10234567890123456);
        }
    }

    void update(int i, long long v){
        i += nn;
        while(i > 0){
            tree[i] = min(tree[i], v);
            i >>= 1;
        }
    }

    long long query(int l, int r){
        long long res = 10234567890123456;
        for(l += nn, r += nn;l < r;l >>= 1, r >>= 1){
            if(l&1){
                res = min(res, tree[l]);
                l++;
            }
            if(r&1){
                r--;
                res = min(res,tree[r]);
            }
        }
        return res;
    }
};

static SegmentTree seg[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> S >> q >> E;
    E--;

    edge edges[n-1];
    for(int i = 0;i < n-1;i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        adj[a].push_back(ii(b,c));
        adj[b].push_back(ii(a,c));
        edges[i] = {a,b,c};
    }

    recurse(0,-1);
    dfs2(0);

    for(int i = 0;i < n;i++){
        parent[i].push_back(ii(i,0));
    }

    for(int i = 0;i < S;i++){
        int x;
        cin >> x;
        x--;
        int preorder = low[x];
        for(ii p : parent[x]){
            disc[p.first].push_back(ii(preorder,p.second));
        }
    }



    for(int i = 0;i < n;i++){
        sort(disc[i].begin(),disc[i].end());
        seg[i].create((int)disc[i].size());
        for(int j = 0;j < disc[i].size();j++){
            ii x = disc[i][j];
            disc2[i].push_back(x.first);
            seg[i].update(j, x.second);
        }
    }

    while(q--){
        int C, R;
        cin >> C >> R;
        C--; R--;

        int subtree;
        int X = edges[C].u;
        int Y = edges[C].v;
        if(depth[X] > depth[Y]){
            subtree = X;
        }
        else{
            subtree = Y;
        }


        int LOW = low[subtree];
        int HIGH = high[subtree];

        bool isRin = (LOW <= low[R] && low[R] <= HIGH);
        bool isEin = (LOW <= low[E] && low[E] <= HIGH);

        if(isRin == isEin){
            cout << "escaped\n";
            continue;
        }

        long long ans = 10234567890123456;
        for(ii P : parent[R]){
            long long res = 10234567890123456;
            int p = P.first;

            bool isPin = (LOW <= low[p] && low[p] <= HIGH);
            if(isPin != isRin){
                continue;
            }
            int lEnd = lower_bound(disc2[p].begin(),disc2[p].end(), LOW) - disc2[p].begin();
            int rEnd = upper_bound(disc2[p].begin(),disc2[p].end(), HIGH) - disc2[p].begin() - 1;
            if(isRin){
                res = min(res, seg[p].query(lEnd,rEnd+1));
            }
            else{
                res = min(res, seg[p].query(0,lEnd));
                res = min(res, seg[p].query(rEnd+1,(int)disc2[p].size()));
            }
            ans = min(ans, res + P.second);
        }



        if(ans > 10234527890123450)
            cout << "oo\n";
        else cout << ans << "\n";
    }

}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:163:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < disc[i].size();j++){
                       ~~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void recurse(int, int)':
valley.cpp:54:9: warning: 'centroid' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int centroid;
         ^~~~~~~~

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