oj.uz

답안 #972436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972436 2024-04-30T12:20:26 Z c2zi6 Valley (BOI19_valley) C++14
100 / 100
 421 ms 69892 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n, s, q, e;
VVPI gp;
VI tin, tout, depth;
int tc;
VVI par;
VVL parv, parw;
VL dp;
VI isshop;

void dfs1(int u, int p, int pw = -1) {
	tin[u] = tc++;
	if (isshop[u]) dp[u] = 0;
	else dp[u] = 1e18;
	for (auto[v, w] : gp[u]) if (v != p) {
		depth[v] = depth[u] + 1;
		dfs1(v, u, w);
		setmin(dp[u], dp[v]+w);
	}
	par[u][0] = p;
	parv[u][0] = dp[u];
	parw[u][0] = pw;
	tout[u] = tc++;
}
bool isanc(int u, int v) {
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}
ll binlift(int u, int k) {
	ll ans = 1e18;
	ll lift = 0;
	rep(i, 20) if (k & (1 << i)) {
		/* cout << (1<<i) << " hat verev elav " << endl; */
		setmin(ans, parv[u][i] + lift);
		lift += parw[u][i];
		u = par[u][i];
	}
	return ans;
}

void solve() {
	cin >> n >> s >> q >> e;
	e--;
	gp = VVPI(n);
	VPI edges;
	rep(i, n-1) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		gp[u].pb({v, w});
		gp[v].pb({u, w});
		edges.pb({u, v});
	}
	isshop = VI(n);
	rep(i, s) {
		int x;
		cin >> x;
		x--;
		isshop[x] = true;
	}
	tin = tout = depth = VI(n);
	tc = 0;
	dp = VL(n);
	par = VVI(n, VI(20));
	parv = VVL(n, VL(20));
	parw = VVL(n, VL(20));
	dfs1(e, e);
	/* rep(u, n) cin >> parv[u][0]; */

	replr(i, 1, 19) rep(u, n) {
		int m = par[u][i-1];
		par[u][i] = par[m][i-1];
		parw[u][i] = parw[u][i-1] + parw[m][i-1];
		parv[u][i] = min(parv[u][i-1], parw[u][i-1] + parv[m][i-1]);
	}
	for (auto&[u, v] : edges) if (!isanc(u, v)) swap(u, v);

	/* rep(u, n) cout << "dp[" << u+1 << "] = " << dp[u] << endl; */

	/* rep(u, n) { */
	/* 	cout << u+1 << ": " << parv[u][0] << " " << parv[u][1] << " " << par[u][2] << endl; */
	/* } */


	while (q--) {
		int edgei, u;
		cin >> edgei >> u;
		edgei--, u--;
		int s = edges[edgei].ss;
		
		if (!isanc(s, u)) {
			cout << "escaped" << endl;
		} else {
			ll ans = binlift(u, depth[u] - depth[s] + 1);
			if (ans == 1e18) cout << "oo" << endl;
			else cout << ans << endl;
		}
	}
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    /* cin >> t; */
    while (t--) solve();
}

Compilation message

valley.cpp: In function 'void dfs1(int, int, int)':
valley.cpp:46:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |  for (auto[v, w] : gp[u]) if (v != p) {
      |           ^
valley.cpp: In function 'void solve()':
valley.cpp:106:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |  for (auto&[u, v] : edges) if (!isanc(u, v)) swap(u, v);
      |            ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 600 KB Output is correct
2 Correct 13 ms 600 KB Output is correct
3 Correct 13 ms 604 KB Output is correct
4 Correct 13 ms 604 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 600 KB Output is correct
2 Correct 13 ms 600 KB Output is correct
3 Correct 13 ms 604 KB Output is correct
4 Correct 13 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 1064 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 868 KB Output is correct
13 Correct 2 ms 1124 KB Output is correct
14 Correct 2 ms 864 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 289 ms 65480 KB Output is correct
2 Correct 295 ms 64864 KB Output is correct
3 Correct 345 ms 64788 KB Output is correct
4 Correct 336 ms 66796 KB Output is correct
5 Correct 394 ms 67016 KB Output is correct
6 Correct 386 ms 69356 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 600 KB Output is correct
2 Correct 13 ms 600 KB Output is correct
3 Correct 13 ms 604 KB Output is correct
4 Correct 13 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 1064 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 868 KB Output is correct
13 Correct 2 ms 1124 KB Output is correct
14 Correct 2 ms 864 KB Output is correct
15 Correct 289 ms 65480 KB Output is correct
16 Correct 295 ms 64864 KB Output is correct
17 Correct 345 ms 64788 KB Output is correct
18 Correct 336 ms 66796 KB Output is correct
19 Correct 394 ms 67016 KB Output is correct
20 Correct 386 ms 69356 KB Output is correct
21 Correct 276 ms 64656 KB Output is correct
22 Correct 285 ms 64196 KB Output is correct
23 Correct 297 ms 64200 KB Output is correct
24 Correct 356 ms 66724 KB Output is correct
25 Correct 357 ms 69876 KB Output is correct
26 Correct 266 ms 64708 KB Output is correct
27 Correct 279 ms 64196 KB Output is correct
28 Correct 299 ms 64200 KB Output is correct
29 Correct 332 ms 65732 KB Output is correct
30 Correct 421 ms 67548 KB Output is correct
31 Correct 270 ms 64708 KB Output is correct
32 Correct 341 ms 64312 KB Output is correct
33 Correct 309 ms 64472 KB Output is correct
34 Correct 348 ms 66504 KB Output is correct
35 Correct 350 ms 69892 KB Output is correct
36 Correct 318 ms 66720 KB Output is correct