Submission #1096309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096309		SmuggingSpun	Valley (BOI19_valley)	C++14	100 / 100	142 ms	37460 KiB

valley

#include<bits/stdc++.h>
#define taskname "landslide"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const ll INF = 1e18;
const int lim = 1e5 + 5;
int t_dfs = 0, U[lim], V[lim], W[lim], low[lim], tail[lim], up[lim][17];
ll dp[lim][17], f[lim];
vector<int>g[lim];
bitset<lim>mark;
void dfs_1(int s, int p = -1){
	if(mark.test(s)){
		dp[s][0] = 0;
	}
	low[s] = ++t_dfs;
	for(int& i : g[s]){
		int d = U[i] ^ V[i] ^ s;
		if(d != p){
			int w = W[i];
			f[d] = f[up[d][0] = s] + w;
			for(int i = 1; i < 17; i++){
				up[d][i] = up[up[d][i - 1]][i - 1];
			}
			dfs_1(d, s);
			minimize(dp[s][0], dp[d][0] + w);
		}
	}
	tail[s] = t_dfs;
}
void dfs_2(int s, int p = -1){
	dp[s][0] -= f[s];
	for(int i = 1; i < 17; i++){
		dp[s][i] = min(dp[s][i - 1], dp[up[s][i - 1]][i - 1]);
	}
	for(int& i : g[s]){
		int d = U[i] ^ V[i] ^ s;
		if(d != p){
			dfs_2(d, s);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	int n, s, q, h;
	cin >> n >> s >> q >> h;
	for(int i = 1; i < n; i++){
		cin >> U[i] >> V[i] >> W[i];
		g[U[i]].emplace_back(i);
		g[V[i]].emplace_back(i);
	}
	mark.reset();
	for(int i = 0; i < s; i++){
		int x;
		cin >> x;
		mark.set(x);
	}
	memset(dp, 0x0f, sizeof(dp));
	memset(up, 0, sizeof(up));
	dfs_1(h);
	dfs_2(h);
	for(int _ = 0; _ < q; _++){
		int I, R;
		cin >> I >> R;
		int u = U[I], v = V[I];
		if(low[u] > low[v]){
			swap(u, v);
		}
		if(low[v] <= low[R] && tail[v] >= low[R]){
			ll ans = INF, temp = f[R];
			for(int i = 16; i > -1; i--){
				int ances = up[R][i];
				if(ances != 0 && low[v] <= low[ances] && tail[v] >= low[ances]){
					minimize(ans, dp[R][i]);
					R = ances;
				}
			}
			minimize(ans, dp[R][0]);
			if(ans + temp > ll(1e16)){
				cout << "oo\n";
				continue;
			}
			cout << ans + temp << "\n";
		}
		else{
			cout << "escaped\n";
		}
	}
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:50:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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