oj.uz

답안 #496562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
496562 2021-12-21T14:37:01 Z Ierus Valley (BOI19_valley) C++17
23 / 100
 455 ms 52728 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 step){
//	cerr << "Get: " << v << " step: " << step << "\n";
	int res = inf;
	for(int i = LG; i >= 0; --i){
		if((step >> i) & 1){
			res = min(res, dp[v][i]);
//			cerr << "DO: " << res << '\n';
			v = up[v][i];
		}
	}
	return res;
}
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, h[edge[i].x] - h[v]) + dist[v]);
		if(cur == inf) cout << "oo\n";
		else cout << cur << '\n';
	}
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 3532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 3532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 376 ms 47676 KB Output is correct
2 Correct 406 ms 47488 KB Output is correct
3 Correct 398 ms 47824 KB Output is correct
4 Correct 430 ms 50028 KB Output is correct
5 Correct 408 ms 50144 KB Output is correct
6 Correct 455 ms 52728 KB Output is correct

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 3532 KB Output isn't correct
2 Halted 0 ms 0 KB -