Submission #429682

#	Time	Username	Problem	Language	Result	Execution time	Memory
429682		fvogel499	Valley (BOI19_valley)	C++14	0 / 100	294 ms	90416 KiB

valley

/*
File created on 06/15/2021 at 19:11:17.
Link to problem: 
Description: 
Time complexity: O()
Space complexity: O()
Status: DEV
Copyright: Ⓒ 2021 Francois Vogel
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define ins insert
#define cls clear

#define int ll
#define ll long long

const int siz = 1e5;
const int inf = 1e18;
const int MAXPOW2 = 19;

vector<pii> graph [siz];
int height [siz];
int par [siz];
bool shop [siz];
int closest [siz];
int up [siz][MAXPOW2];
int minAcross [siz][MAXPOW2];
int disc [siz];
int rightMost [siz];

void dfs(int cn, int ch) {
    height[cn] = ch;
    for (pii e : graph[cn]) if (par[cn] != e.f) {
        par[e.f] = cn;
        dfs(e.f, ch+e.s);
    }
}

void closestShop(int cn) {
    closest[cn] = inf;
    if (shop[cn]) closest[cn] = height[cn];
    for (pii e : graph[cn]) if (par[cn] != e.f) {
        closestShop(e.f);
        closest[cn] = min(closest[cn], closest[e.f]);
    }
}

int tim;
int eulerTour(int cn) {
    disc[cn] = rightMost[cn] = tim++;
    for (pii e : graph[cn]) if (e.f != par[cn]) {
        rightMost[cn] = eulerTour(e.f);
    }
    return rightMost[cn];
}

int jmp(int x, int d) {
    int mnv = inf;
    for (int i = 0; i < MAXPOW2; i++) if ((d>>i)&1) {
        mnv = min(mnv, minAcross[x][i]);
        x = up[x][i];
    }
    return mnv;
}

signed main() {
    cin.tie(0);
    // ios_base::sync_with_stdio(0);

    int n, nbShops, nbReq, root;
    cin >> n >> nbShops >> nbReq >> root;
    root--;
    pii roads [n-1];
    for (int i = 0; i < n-1; i++) {
        int nA, nB, lW;
        cin >> nA >> nB >> lW;
        nA--;
        nB--;
        graph[nA].pb(pii(nB, lW));
        graph[nB].pb(pii(nA, lW));
        roads[i] = pii(nA, nB);
    }
    par[root] = -1;
    dfs(root, 0);
    for (int i = 0; i < n; i++) shop[i] = false;
    for (int i = 0; i < nbShops; i++) {
        int node;
        cin >> node;
        node--;
        shop[node] = true;
    }
    closestShop(root);
    for (int i = 0; i < n; i++) if (closest[i] != inf) closest[i] -= height[i]*2;
    for (int i = 0; i < n; i++) {
        up[i][0] = par[i];
        minAcross[i][0] = closest[i];
    }
    for (int i = 1; i < MAXPOW2; i++) for (int j = 0; j < n; j++) {
        if (up[j][i-1] != -1) {
            minAcross[j][i] = min(minAcross[j][i-1], minAcross[up[j][i-1]][i-1]);
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }
    eulerTour(root);
    for (int i = 0; i < nbReq; i++) {
        int blocked;
        cin >> blocked;
        blocked--;
        if (height[roads[blocked].f] > height[roads[blocked].s]) blocked = roads[blocked].f;
        else blocked = roads[blocked].s;
        int cur;
        cin >> cur;
        cur--;
        cout << "--> ";
        if (disc[blocked] <= disc[cur] and disc[cur] <= rightMost[blocked]) {
            int res = jmp(cur, height[cur]-height[blocked]+1);
            if (res == inf) {
                cout << "oo" << endl;
                continue;
            }
            res += height[cur];
            cout << res << endl;
        }
        else {
            cout << "escaped" << endl;
        }
    }

    int d = 0;
    d++;
}

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