oj.uz

Submission #496570

# Submission time Handle Problem Language Result Execution time Memory
496570 2021-12-21T14:46:50 Z Ierus Valley (BOI19_valley) C++17
100 / 100
 513 ms 54604 KB 
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define int long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
const bool I = 1;
const int LG = 19;
int up[N][LG+2], tin[N], tout[N], timer, dp[N][LG+2];
int n, s, q, e, h[N], dist[N];
bool mag[N];
struct edge{int x, y, w;}edge[N];
vector<pair<int,int>> g[N];
vector<int> d(N, inf);
void dfs(int v, int p = 1){
	tin[v] = ++timer;
	h[v] = h[p] + 1;
	if(mag[v]) d[v] = 0;
	for(auto to : g[v]){
		if(to.F == p) continue;
		dist[to.F] = dist[v] + to.S;
		dfs(to.F, v);
 		d[v] = min(d[v], d[to.F] + to.S);
	}
	tout[v] = timer;
}
void dfs1(int v, int p) {
	up[v][0] = p;
	dp[v][0] = min(d[v] - dist[v], d[p] - dist[p]);
	for (int i = 1; i <= LG; ++i){
		up[v][i] = up[up[v][i-1]][i-1];
		dp[v][i] = min(dp[v][i-1], dp[up[v][i-1]][i-1]);	
	}
	for (auto to: g[v]){
		if (to.F != p){
			dfs1(to.F, v);
		}
	}
}
bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a] ;
}
//int lca (int a, int b){
//	if (upper(a, b)) return a;
//	if (upper(b, a)) return b;
//	for (int i = LG; i>=0; --i)
//		if (!upper(up[a][i], b))
//			a = up[a][i];
//	return up[a][0];
//}
int get(int v, int u){
	if(v == u) return d[v] - dist[u];
//	cerr << "Get: " << v << " step: " << step << "\n";
	int res = inf;
	for(int i = LG; i >= 0; --i){
		if(!upper(up[v][i], u)){
			res = min(res, dp[v][i]);
			
//			cerr << "DO: " << res << '\n';
			v = up[v][i];
		}
	}
	return min(res,dp[v][0]);
}
signed main(){
	cin >> n >> s >> q >> e;
	for(int i = 1; i < n; ++i){
		int x, y, w;
		cin >> x >> y >> w;
		g[x].pb({y, w});
		g[y].pb({x, w});
		edge[i] = {x, y, w};
	}
	for(int i = 1; i <= s; ++i){
		int xx; cin >> xx;
		mag[xx] = true;
	}
	dfs(e, e);
	dfs1(e,e);
//	for(int i = 1; i <= n; ++i){
//		cout << "d["<<i<<"]: " << d[i] << '\n';
//	}
//	for(int i = 1; i <= n; ++i){
//		cout << "dist["<<i<<"]: " << dist[i] << '\n';
//	}
	for(int i, v; q--;){
		cin >> i >> v;
		if(h[edge[i].x] < h[edge[i].y]){
			swap(edge[i].x, edge[i].y);
		}
//		cerr << "x: " << edge[i].x << " lca: " << lca(edge[i].x, v) << '\n';
		if(!upper(edge[i].x, v)){
			cout << "escaped\n";
			continue;
		}
		int cur = min(d[v], get(v, edge[i].x) + dist[v]);
		if(cur == inf) cout << "oo\n";
		else cout << cur << '\n';
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3532 KB Output is correct
2 Correct 21 ms 3616 KB Output is correct
3 Correct 24 ms 3604 KB Output is correct
4 Correct 18 ms 3656 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3532 KB Output is correct
2 Correct 21 ms 3616 KB Output is correct
3 Correct 24 ms 3604 KB Output is correct
4 Correct 18 ms 3656 KB Output is correct
5 Correct 5 ms 3864 KB Output is correct
6 Correct 4 ms 3916 KB Output is correct
7 Correct 4 ms 3884 KB Output is correct
8 Correct 6 ms 3916 KB Output is correct
9 Correct 5 ms 3864 KB Output is correct
10 Correct 5 ms 3916 KB Output is correct
11 Correct 5 ms 3948 KB Output is correct
12 Correct 7 ms 3940 KB Output is correct
13 Correct 5 ms 3940 KB Output is correct
14 Correct 4 ms 3992 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 47684 KB Output is correct
2 Correct 447 ms 47480 KB Output is correct
3 Correct 400 ms 47760 KB Output is correct
4 Correct 456 ms 50060 KB Output is correct
5 Correct 423 ms 50076 KB Output is correct
6 Correct 490 ms 52624 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3532 KB Output is correct
2 Correct 21 ms 3616 KB Output is correct
3 Correct 24 ms 3604 KB Output is correct
4 Correct 18 ms 3656 KB Output is correct
5 Correct 5 ms 3864 KB Output is correct
6 Correct 4 ms 3916 KB Output is correct
7 Correct 4 ms 3884 KB Output is correct
8 Correct 6 ms 3916 KB Output is correct
9 Correct 5 ms 3864 KB Output is correct
10 Correct 5 ms 3916 KB Output is correct
11 Correct 5 ms 3948 KB Output is correct
12 Correct 7 ms 3940 KB Output is correct
13 Correct 5 ms 3940 KB Output is correct
14 Correct 4 ms 3992 KB Output is correct
15 Correct 380 ms 47684 KB Output is correct
16 Correct 447 ms 47480 KB Output is correct
17 Correct 400 ms 47760 KB Output is correct
18 Correct 456 ms 50060 KB Output is correct
19 Correct 423 ms 50076 KB Output is correct
20 Correct 490 ms 52624 KB Output is correct
21 Correct 367 ms 48432 KB Output is correct
22 Correct 369 ms 48176 KB Output is correct
23 Correct 418 ms 49112 KB Output is correct
24 Correct 440 ms 50988 KB Output is correct
25 Correct 440 ms 54604 KB Output is correct
26 Correct 366 ms 48536 KB Output is correct
27 Correct 416 ms 48400 KB Output is correct
28 Correct 410 ms 48492 KB Output is correct
29 Correct 426 ms 50272 KB Output is correct
30 Correct 513 ms 52140 KB Output is correct
31 Correct 377 ms 49344 KB Output is correct
32 Correct 383 ms 48416 KB Output is correct
33 Correct 424 ms 48656 KB Output is correct
34 Correct 435 ms 50940 KB Output is correct
35 Correct 440 ms 54340 KB Output is correct
36 Correct 463 ms 51416 KB Output is correct