Submission #337933

#	Time	Username	Problem	Language	Result	Execution time	Memory
337933		Kevin_Zhang_TW	Valley (BOI19_valley)	C++17	100 / 100	204 ms	34156 KiB

valley

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
	return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
	return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 100010, MAX_K = 17;
const ll inf = 1ll << 60, bound = 1e15;
int n, s, q, e;

vector<pair<int,int>> edge[MAX_N];
bool shop[MAX_N];
int anc[MAX_K][MAX_N], in[MAX_N], out[MAX_N];
ll dp[MAX_K][MAX_N], dep[MAX_N];
inline bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
void dfs(int x, int lst) {
	static int t;
	in[x] = ++t;
	anc[0][x] = lst;
	dp[0][x] = shop[x] ? dep[x] : inf;
	for (auto [u, w] : edge[x]) if (u != lst) {
		dep[u] = dep[x] + w;
		dfs(u, x);
		chmin(dp[0][x], dp[0][u]);
	}
	out[x] = t;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> s >> q >> e;
	vector<pair<int,int>> alle(n);
	for (int a, b, w, i = 1;i < n;++i) {
		cin >> a >> b >> w;
		alle[i] = {a, b};
		edge[a].pb(b, w);
		edge[b].pb(a, w);
	}
	for (int p, i = 0;i < s;++i) {
		cin >> p;
		shop[p] = true;
	}
	dfs(e, 0);
	for (int i = 1;i <= n;++i) {
		dp[0][i] -= 2 * dep[i];
	}

	int mxlg = 0;

	for (int b = 1;b < MAX_K;++b) {
		mxlg = b;
		for (int i = 1;i <= n;++i) {
			anc[b][i] = anc[b-1][ anc[b-1][i] ];
			dp[b][i] = min(dp[b-1][i], dp[b-1][ anc[b-1][i] ]);
		}
	}

	while (q--) {
		int ID, R;
		cin >> ID >> R;
		auto [a, b] = alle[ID];
		if (dep[a] > dep[b]) swap(a, b);
		// a is up
		// b is down
		if (!isanc(b, R)) cout << "escaped\n";
		else if (shop[R]) cout << 0 << '\n';
		else {
			ll res = inf;
			int x = R;
			for (int d = mxlg;d >= 0;--d) {
				if (isanc(a, anc[d][x])) {
					DE(a, x, anc[d][x]);
					chmin(res, dp[d][x] + dep[R]);
					x = anc[d][x];
				}
			}
			
			if (res > bound)
				cout << "oo\n";
			else cout << res << '\n';
		}
	}
}

Compilation message (stderr)

valley.cpp: In function 'int32_t main()':
valley.cpp:20:17: warning: statement has no effect [-Wunused-value]
   20 | #define DE(...) 0
      |                 ^
valley.cpp:92:6: note: in expansion of macro 'DE'
   92 |      DE(a, x, anc[d][x]);
      |      ^~

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