Submission #1133578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133578		thelegendary08	Valley (BOI19_valley)	C++17	100 / 100	154 ms	50912 KiB

valley

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 1e5 + 5;
vi par(mxn, -1);
vpii adj[mxn];
int magic[mxn];
vb shop(mxn);
vi dist(mxn, 4e18);
vi pos(mxn);
vi sz(mxn);
vi dep(mxn, 0);
int timer = 0;
int dfs(int x, int from){
	if(from != -1){
		dep[x] = dep[from] + 1;
	}
	pos[x] = timer;
	timer++;
	int cur = 1;
	for(auto u : adj[x]){
		if(u.first != from){
			cur += dfs(u.first, x);
		}
	}
	sz[x] = cur;
	return cur;
}
bool in_subtree(int big, int small){
	//dout2(big,small);
	//out3(sz[big], pos[big], pos[small]);
	return pos[small] <= pos[big] + sz[big] - 1 && pos[small] >= pos[big];
}
void build_magic(int x, int from){
	for(auto u : adj[x]){
		if(u.first != from){
			build_magic(u.first, x);
		}
	}
	if(shop[x])magic[x] = dist[x];
	else magic[x] = 4e18;
	for(auto u : adj[x]){
		if(u.first != from){
			magic[x] = min(magic[x], magic[u.first]);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	in4(n,s,Q,e);
	e--;
	
	vpii edges;
	f0r(i,n-1){
		in3(a,b,w);
		a--;
		b--;
		adj[a].pb(mp(b,w));
		adj[b].pb(mp(a,w));
		edges.pb({a,b});
	}
	f0r(i, s){
		in(x);
		x--;
		shop[x] = 1;
	}
	dist[e] = 0;
	queue<int>q;
	q.push(e);
	while(!q.empty()){
		int node = q.front();
		q.pop();
		for(auto u : adj[node]){
			if(dist[u.first] == 4e18){
				par[u.first] = node;
				dist[u.first] = dist[node] + u.second;
				q.push(u.first);
			}
		}
	}
	dfs(e, -1);
	build_magic(e, -1);
	//f0r(i, n)cout<<par[i]<<' ';
	//cout<<'\n';
	f0r(i,n){
		if(magic[i] != 4e18)magic[i] -= 2 * dist[i];
	}
	vvi jmp(n, vi(17, -1));
	f0r(i,n){
		jmp[i][0] = par[i];
	}
	FOR(i, 1, 17){
		f0r(j,n){
			if(jmp[j][i-1] != -1)jmp[j][i] = jmp[jmp[j][i-1]][i-1];
			else jmp[j][i] = -1;
		}
	}
	vvi magicjmp(n, vi(17, 4e18));
	f0r(i,n){
		magicjmp[i][0] = magic[i];
	}
	FOR(i, 1, 17){
		f0r(j,n){
			int pr = jmp[j][i-1];
			if(pr != -1 && magicjmp[pr][i-1] != 4e18)magicjmp[j][i] = min(magicjmp[j][i-1], magicjmp[pr][i-1]);
		}
	}
	//f0r(i,n)cout<<magic[i]<<' ';
	//cout<<'\n';
	//f0r(i,n)cout<<dep[i]<<' ';
	//cout<<'\n';
	while(Q--){
		in2(road, start);
		
		road--;
		start--;
		int top = edges[road].first;
		int bottom = edges[road].second;
		if(par[edges[road].first] == edges[road].second)swap(top,bottom);
		//dout2(top,bottom);
		//out(in_subtree(bottom, start));
		
		if(!in_subtree(bottom, start))out("escaped");
		else{
			//path minimum from start to bottom
			
			int cur = magic[start];
			int curnode = par[start];
			int travel = dep[start] - dep[bottom];
			//out3(cur, curnode, travel);
			
			
			f0r(i, 17){
				if(travel & (1 << i)){
					cur = min(cur, magicjmp[curnode][i]);
					curnode = jmp[curnode][i];
				}
			}
			//out2(curnode, bottom);
			//out2(cur, dist[start]);
			if(cur != 4e18)out(cur + dist[start]);
			else out("oo");
		}
		
		
	}
	
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41