oj.uz

Submission #498535

# Submission time Handle Problem Language Result Execution time Memory
498535 2021-12-25T12:05:41 Z s_samchenko Valley (BOI19_valley) C++17
59 / 100
 310 ms 64448 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e15;
const ll mod = 1e9+7;
const int N = 2e5+100;

vector <int> p(N), d(N), ds(N);
vector < vector <pii> > g(N);
vector < vector <int> > up(N, vector <int> (20));
vector <pair <pii, int> > edges(N);
vector <int> c(N);
int n, s, q, r;

void dfs(int v, int pr, int l = 0, int h = 1){
	d[v] = h;
	ds[v] = l;
	up[v][0] = pr;
	for (int j = 1; j < 20; ++j) up[v][j] = up[up[v][j-1]][j-1];
	
	for (auto i : g[v]){
		int to = i.ff, len = i.ss;
		if (to == pr) continue;
		dfs(to, v, l + len, h+1);
	}
}

int lca(int u, int v){
	if (d[u] > d[v]) swap(u, v);
	for (int j = 19, H = d[v] - d[u]; H && j >= 0; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		v = up[v][j];
	}
	if (u == v) return u;
	for (int j = 19; j >= 0; --j){
		int u1 = up[u][j], v1 = up[v][j];
		if (u1 != v1){
			u = u1; v = v1;
		}
	}
	return up[u][0];
}

void sol3(){
	while (q--){
		int ir, v, x, y;
		cin >> ir >> v;
		x = edges[ir].ff.ff, y = edges[ir].ff.ss;
		
		int w1 = lca(v, x), w2 = lca(v, y);
		if (w1 == x && w2 == y) cout << "0\n";
		else cout << "escaped\n";
	}
}

void sol12(){
	while (q--){
		int ir, v, x, y;
		cin >> ir >> v;
		x = edges[ir].ff.ff, y = edges[ir].ff.ss;
		
		vector <int> u(n+10); u[v] = 1;
		queue <int> q; q.push(v);
		for (int i = 1; i <= n; ++i) d[i] = inf;
		d[v] = 0;
		while (!q.empty()){
			v = q.front(); q.pop();
			for (auto [to, len] : g[v]){
				if (v == x && to == y || v == y && to == x) continue;
				if (u[to]) continue;
				u[to] = 1;
				d[to] = d[v] + len;
				q.push(to);
			}
		}
		
		if (d[r] != inf){
			cout << "escaped\n";
			continue;
		}
		int best = inf;
		for (int i = 1; i <= n; ++i)
			if (c[i]) best = min(best, d[i]);
		if (best == inf) cout << "oo\n";
		else cout << best << '\n';
	}
}

void solve(){
	cin >> n >> s >> q >> r;
	for (int i = 1; i < n; ++i){
		int a, b, w; cin >> a >> b >> w;
		g[a].pb({b, w});
		g[b].pb({a, w});
		edges[i] = {{a, b}, w};
	}
	for (int i = 0; i < s; ++i){
		int a; cin >> a; c[a] = 1;
	}
	
	dfs(r, r);
	
	if (s == n){
		sol3(); return;
	}
	
	if (n*q <= 1e6){
		sol12();
		return;
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;

	while (tt--){
		solve();
		cout << '\n';
	}
}

Compilation message

valley.cpp: In function 'void sol12()':
valley.cpp:86:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   86 |     if (v == x && to == y || v == y && to == x) continue;
      |         ~~~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55216 KB Output is correct
2 Correct 51 ms 55228 KB Output is correct
3 Correct 50 ms 55164 KB Output is correct
4 Correct 37 ms 55144 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55216 KB Output is correct
2 Correct 51 ms 55228 KB Output is correct
3 Correct 50 ms 55164 KB Output is correct
4 Correct 37 ms 55144 KB Output is correct
5 Correct 44 ms 55220 KB Output is correct
6 Correct 47 ms 55152 KB Output is correct
7 Correct 55 ms 55160 KB Output is correct
8 Correct 43 ms 55160 KB Output is correct
9 Correct 47 ms 55148 KB Output is correct
10 Correct 55 ms 55164 KB Output is correct
11 Correct 36 ms 55200 KB Output is correct
12 Correct 34 ms 55108 KB Output is correct
13 Correct 34 ms 55112 KB Output is correct
14 Correct 55 ms 55148 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 61064 KB Output is correct
2 Correct 211 ms 60772 KB Output is correct
3 Correct 226 ms 61072 KB Output is correct
4 Correct 295 ms 62700 KB Output is correct
5 Correct 290 ms 62656 KB Output is correct
6 Correct 310 ms 64448 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55216 KB Output is correct
2 Correct 51 ms 55228 KB Output is correct
3 Correct 50 ms 55164 KB Output is correct
4 Correct 37 ms 55144 KB Output is correct
5 Correct 44 ms 55220 KB Output is correct
6 Correct 47 ms 55152 KB Output is correct
7 Correct 55 ms 55160 KB Output is correct
8 Correct 43 ms 55160 KB Output is correct
9 Correct 47 ms 55148 KB Output is correct
10 Correct 55 ms 55164 KB Output is correct
11 Correct 36 ms 55200 KB Output is correct
12 Correct 34 ms 55108 KB Output is correct
13 Correct 34 ms 55112 KB Output is correct
14 Correct 55 ms 55148 KB Output is correct
15 Correct 181 ms 61064 KB Output is correct
16 Correct 211 ms 60772 KB Output is correct
17 Correct 226 ms 61072 KB Output is correct
18 Correct 295 ms 62700 KB Output is correct
19 Correct 290 ms 62656 KB Output is correct
20 Correct 310 ms 64448 KB Output is correct
21 Incorrect 114 ms 62640 KB Output isn't correct
22 Halted 0 ms 0 KB -