Submission #856704

#	Time	Username	Problem	Language	Result	Execution time	Memory
856704		vjudge1	Valley (BOI19_valley)	C++14	100 / 100	146 ms	39460 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define task ""

const int MAX = 100010;
int n, s, q, e;
long long INF;
bool shop[MAX];
pair<int, int> edges[MAX];
vector<pair<int, int>> adj[MAX];

int timer, tin[MAX], tout[MAX], h[MAX];
long long dep[MAX], minD[MAX][2];

void preDfs(int u, int p) {
    tin[u] = ++timer;
    if (shop[u]) minD[u][0] = 0;
    for (pair<int, int> &e: adj[u]) if (e.first != p) {
        int v = e.first, w = e.second;
        dep[v] = dep[u] + w;
        h[v] = h[u] + 1;
        preDfs(v, u);
        if (minD[u][0] >= minD[v][0] + w) {
            minD[u][1] = minD[u][0];
            minD[u][0] = minD[v][0] + w;
        } else minD[u][1] = min(minD[u][1], minD[v][0] + w);
    }
    tout[u] = timer;
}

long long getD(int u, int v, int w) {
    return minD[u][0] == minD[v][0] + w ? minD[u][1] : minD[u][0] - dep[u];
}

long long dp[17][MAX];
int anc[17][MAX];

void dfs(int u, int p) {
    for (pair<int, int> &e: adj[u]) if (e.first != p) {
        int v = e.first, w = e.second;
        dp[0][v] = getD(u, v, w);
        anc[0][v] = u;
        for (int j = 1; j <= 16; ++j) {
            anc[j][v] = anc[j - 1][anc[j - 1][v]];
            dp[j][v] = min(dp[j - 1][v], dp[j - 1][anc[j - 1][v]]);
        }
        dfs(v, u);
    }
}

bool isAnc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

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

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

	cin >> n >> s >> q >> e;
	for (int i = 1; i < n; ++i) {
        int u, v, w; cin >> u >> v >> w;
        edges[i] = make_pair(u, v);
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
	}
	for (int i = 1; i <= s; ++i) {
        int u; cin >> u;
        shop[u] = true;
	}
	memset(minD, 0x3f, sizeof minD); INF = minD[0][0];
	preDfs(e, -1);
	dfs(e, -1);
	while (q--) {
        int id, R; cin >> id >> R;
        int u = edges[id].first, v = edges[id].second;
        if (tin[u] > tin[v]) swap(u, v);
        if (isAnc(v, R) == false) {
            cout << "escaped\n";
            continue;
        }
        long long ans = minD[R][0];
        if (v != R) {
            u = R;
            for (int j = 0, k = h[R] - h[v]; (1 << j) <= k; ++j) {
                if (k >> j & 1) {
                    ans = min(ans, dep[R] + dp[j][u]);
                    u = anc[j][u];
                }
            }
        }
        if (ans == INF) cout << "oo\n";
        else cout << ans << '\n';
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:59:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:60:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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