Submission #1275414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275414		SoMotThanhXuan	Valley (BOI19_valley)	C++17	100 / 100	113 ms	39192 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define FOR(i , a, b)for(int i = a; i <= b; i++)
#define REP(i , a, b) for(int i = b ;i >= a;i--)
#define ALL(v) v.begin() , v.end()
#define pb push_back
#define F first
#define S second
#define pii pair<int ,int>
bool minimize(int& a, int b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
bool minimizell(long long& a, long long b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
bool maximize(int& a, int b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
bool maximizell(long long& a, long long b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
const int maxN = 1e5 + 999;
vector<pii> e[maxN];
int n , q, numHouse, escape;
int cost[maxN];
int house[maxN];
pii Edge[maxN];
const long long MAXLL = 1e18 +9;
namespace sub1{
	 bool check(){
		return (n <= 1000);
	 }
	 long long d[maxN];
	 bool vis[maxN];
	 void dfs(int u, int collapse){
		vis[u] = 1;
		for(auto X  : e[u]){
			int x = X.F , id = X.S;
			if(vis[x] || id == collapse)continue;
			d[x] = d[u] + cost[id];
			dfs(x, collapse);
		}
	 }
	 void solve(){
		FOR(xcxc, 1, q){
			int collapse ,root;
			cin >> collapse >> root;
			FOR(i, 1, n)vis[i] = 0;
			d[root] = 0;
			dfs(root, collapse);
			if(vis[escape]){
				cout << "escaped" << '\n';
				continue;
			}
			long long mndis = MAXLL;
			FOR(u , 1 ,numHouse){
				if(vis[house[u]])minimizell(mndis , d[house[u]]);
			}
			if(mndis ==  MAXLL)cout << "oo" << '\n';
			else cout << mndis << '\n';

		}



	 }

}
namespace ac{
	int dep[maxN];
	long long dp[maxN] , f[maxN];
	long long mx[maxN][20];
	int in[maxN] , out[maxN], TICK;
	int T[maxN][20];
	void pre(int u ,int p){
		in[u] = out[u] = ++TICK;
		for(auto X : e[u]){
			int x = X.F ,id = X.S;
			if(x == p)continue;
			dep[x] = dep[u] + 1;
			T[x][0] = u;
			f[x] = f[u] + cost[id];
			pre(x, u);
			minimizell(dp[u] , dp[x] + cost[id]);
		}
		out[u] = TICK;
	}
	bool isP(int p ,int u){
		return (in[p] <= in[u] && out[u] <= out[p]);
	}
	long long jump(int u ,int p){
		long long ans = MAXLL;
		REP(i, 0 , 18){
			if(dep[u] - dep[p] >= (1 << i)){
//					cout << i << " "<<u << " " << T[u][i] <<  " " << mx[u][i] << '\n';
				minimizell(ans, mx[u][i]);
				u = T[u][i];
			}
		}
		minimizell(ans, dp[u] - f[u]);
//		cout << u << '\n';
		return ans;
	}
	void solve(){
		FOR(u, 1, n)dp[u] = MAXLL;
		FOR(i  ,1 ,numHouse)dp[house[i]] = 0;
		pre(escape ,0);
		FOR(u, 1, n){
			mx[u][0] = dp[u] - f[u];
		}
		FOR(i, 1 , 18){
			FOR(u, 1, n){
				T[u][i] = T[T[u][i - 1]][i - 1];
				mx[u][i] = min(mx[u][i - 1] , mx[T[u][i - 1]][i -  1]);
			}
		}
		FOR(xcxc, 1, q){
			int collapse ,x;
			cin >> collapse >> x;
			int u = Edge[collapse].F , v = Edge[collapse].S;
			if(dep[u] < dep[v])swap(u ,v);
			/// dep[u] <= dep[v]
			if(isP(u ,x)){
				long long ans = MAXLL;
				minimizell(ans, dp[x]);
				long long k =  jump(x , u);
				minimizell(ans ,k + f[x]);
//				cout << dp[3] - f[3] + f[5];
				if(ans > 1e17)cout << "oo" << '\n';
				else cout << ans << '\n';

			}else{
				cout << "escaped" << '\n';
			}


		}

	}

}
void solve(){
	cin >> n >> numHouse >> q >> escape;
	FOR(i, 1 , n - 1){
		int u , v ;
		cin >> u >> v >> cost[i];
		e[u].pb({v, i});
		e[v].pb({u ,i});
		Edge[i] = {u , v};
	}
	FOR(i, 1, numHouse)cin >> house[i];
	if(sub1::check())return sub1::solve();
	ac::solve();



}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

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