oj.uz

Submission #405510

# Submission time Handle Problem Language Result Execution time Memory
405510 2021-05-16T13:40:18 Z knightron0 Valley (BOI19_valley) C++14
100 / 100
 363 ms 178228 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e5 + 5;

vector<pair<int, int>> adj[MAXN];
int up[MAXN][100], upmn[MAXN][100], depth[MAXN], dist[MAXN];
vector<pair<int, int>> edges;
bool flag[MAXN];
int timer = 0, n, l;
int tout[MAXN], tin[MAXN];
int dp[MAXN];

void dfs(int v, int p, int d, int dpth){
	timer++;
	dist[v] = d;
	depth[v] = dpth;
	tin[v] = timer;
	up[v][0] = p;
	for(int i=1;i<=l;i++){
		up[v][i] = up[up[v][i-1]][i-1];
	}
	for(auto &[u, w]: adj[v]){
		if(u != p){
			dfs(u, v, d+w, dpth+1);
		}
	}
	timer++;
	tout[v] = timer;
}

bool isanc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

void preprocess(){
	timer = 0;
	clr(tout, 0);
	clr(tin, 0);
	l = 20;
	clr(flag, 0);
	clr(depth, 0);
	clr(up, 0);
	clr(dist, 0);
}

int lca(int u, int v){
	if(isanc(u, v)) return u;
	if(isanc(v, u)) return v;
	for(int i = l;i >= 0;i--){
        if(!isanc(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

int dfs0(int u, int p){
	int ans = INF;
	if(flag[u]) ans = dist[u];
	for(auto &[v, w]: adj[u]){
		if(v == p) continue;
		ans = min(ans, dfs0(v, u));
	}
	dp[u] = -2* dist[u] + ans;
	return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
	int n, c, q, s;
	cin>>n>>c>>q>>s;
	preprocess();
	for(int i=0;i<n-1;i++){
		int u, v, w;
		cin>>u>>v>>w;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
		edges.pb({u, v});
	}
	
	for(int i=0;i<c;i++){
		int x; cin>>x;
		flag[x] = true;
	}
	dfs(s, s, 0, 0);
	dfs0(s, -1);
	for(int i=1;i<=n;i++){
		upmn[i][0] = dp[up[i][0]];
	}
	for(int i=1;i<=l;i++){
		for(int j = 1;j<=n;j++){
			upmn[j][i]= min(upmn[j][i-1], upmn[up[j][i-1]][i-1]);
		}
	}
	while(q--){
		int i, u;
		cin>>i>>u;
		i--;
		int root = -1;
		if(depth[edges[i].fr] < depth[edges[i].sc]){
			root = edges[i].sc;
		} else {
			root = edges[i].fr;
		}
		if(!isanc(root, u)){
			cout<<"escaped"<<endl;
			continue;
		}
		int curr = u;
		int ans = dp[u];
		for(int i = l;i >= 0;i--){
			if(depth[up[curr][i]] >= depth[root]){
				ans = min(ans, upmn[curr][i]);
				curr = up[curr][i];
			}
		}
		if(ans+dist[u] >= 1e14){
			cout<<"oo"<<endl;
		} else {
			cout<<ans+dist[u]<<endl;
		}
	
	}
    return 0;
}

Compilation message

valley.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
valley.cpp:38:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |  for(auto &[u, w]: adj[v]){
      |            ^
valley.cpp: In function 'long long int dfs0(long long int, long long int)':
valley.cpp:75:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |  for(auto &[v, w]: adj[u]){
      |            ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 84288 KB Output is correct
2 Correct 39 ms 84392 KB Output is correct
3 Correct 38 ms 84384 KB Output is correct
4 Correct 38 ms 84360 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 84288 KB Output is correct
2 Correct 39 ms 84392 KB Output is correct
3 Correct 38 ms 84384 KB Output is correct
4 Correct 38 ms 84360 KB Output is correct
5 Correct 37 ms 85056 KB Output is correct
6 Correct 39 ms 85068 KB Output is correct
7 Correct 38 ms 85064 KB Output is correct
8 Correct 40 ms 84976 KB Output is correct
9 Correct 37 ms 85060 KB Output is correct
10 Correct 37 ms 85060 KB Output is correct
11 Correct 37 ms 85012 KB Output is correct
12 Correct 39 ms 85044 KB Output is correct
13 Correct 37 ms 85052 KB Output is correct
14 Correct 37 ms 84956 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 174464 KB Output is correct
2 Correct 307 ms 174280 KB Output is correct
3 Correct 355 ms 174584 KB Output is correct
4 Correct 348 ms 175920 KB Output is correct
5 Correct 319 ms 176168 KB Output is correct
6 Correct 361 ms 177760 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 84288 KB Output is correct
2 Correct 39 ms 84392 KB Output is correct
3 Correct 38 ms 84384 KB Output is correct
4 Correct 38 ms 84360 KB Output is correct
5 Correct 37 ms 85056 KB Output is correct
6 Correct 39 ms 85068 KB Output is correct
7 Correct 38 ms 85064 KB Output is correct
8 Correct 40 ms 84976 KB Output is correct
9 Correct 37 ms 85060 KB Output is correct
10 Correct 37 ms 85060 KB Output is correct
11 Correct 37 ms 85012 KB Output is correct
12 Correct 39 ms 85044 KB Output is correct
13 Correct 37 ms 85052 KB Output is correct
14 Correct 37 ms 84956 KB Output is correct
15 Correct 279 ms 174464 KB Output is correct
16 Correct 307 ms 174280 KB Output is correct
17 Correct 355 ms 174584 KB Output is correct
18 Correct 348 ms 175920 KB Output is correct
19 Correct 319 ms 176168 KB Output is correct
20 Correct 361 ms 177760 KB Output is correct
21 Correct 278 ms 173944 KB Output is correct
22 Correct 284 ms 173828 KB Output is correct
23 Correct 294 ms 173872 KB Output is correct
24 Correct 339 ms 175576 KB Output is correct
25 Correct 340 ms 178228 KB Output is correct
26 Correct 324 ms 174128 KB Output is correct
27 Correct 278 ms 173748 KB Output is correct
28 Correct 317 ms 173996 KB Output is correct
29 Correct 321 ms 175200 KB Output is correct
30 Correct 363 ms 176432 KB Output is correct
31 Correct 301 ms 174000 KB Output is correct
32 Correct 292 ms 173852 KB Output is correct
33 Correct 300 ms 174016 KB Output is correct
34 Correct 342 ms 175548 KB Output is correct
35 Correct 350 ms 177980 KB Output is correct
36 Correct 329 ms 175536 KB Output is correct