Submission #976392

#	Time	Username	Problem	Language	Result	Execution time	Memory
976392		ByeWorld	Valley (BOI19_valley)	C++14	23 / 100	378 ms	69784 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
const int MAXN = 2e5+10;
const int INF = 1e18+10;
const int LOG = 18; 
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;

int n, s, q, e;
int u[MAXN], v[MAXN], w[MAXN], type[MAXN];
vector <ipii> adj[MAXN];

int par[MAXN], dep[MAXN], in[MAXN], out[MAXN], tim;
int arr[MAXN], chi[MAXN];
void dfs(int nw, int pa){
	par[nw] = pa; in[nw] = ++tim; arr[tim] = nw;
	dep[nw] = dep[pa]+1;
	for(auto ed : adj[nw]){
		int nx = ed.fi.fi, idx = ed.se;
		if(nx==pa) continue;
		chi[idx] = nx;
		dfs(nx, nw);
	}
	out[nw] = ++tim; arr[tim] = -nw;
}

struct fen {
	int st[2*MAXN];
	void upd(int x, int p){
		for(; x<=2*MAXN-20; x+=(x&(-x))) st[x] += p;
	}
	int que(int x){
		int te = 0;
		for(; x>=1; x-=(x&(-x))) te += st[x];
		return te;
	}
} A;

int cpar[MAXN], csiz[MAXN], cdep[MAXN], val[MAXN];
int ans[MAXN], cchi[MAXN], IDX[MAXN], STA[MAXN], dist[MAXN][LOG];
bool rem[MAXN];
vector <int> cari[MAXN];

void pre(int nw, int pa){
	csiz[nw] = 1;
	for(auto ed : adj[nw]){
		int nx = ed.fi.fi;
		if(rem[nx] || nx==pa) continue;
		pre(nx, nw);
		csiz[nw] += csiz[nx];
	}
}
int find(int nw){
	pre(nw, -1);
	bool found = 0; int ret = nw, sta = csiz[nw];
	while(!found){
		found = 1;
		for(auto ed : adj[ret]){
			int nx = ed.fi.fi;
			if(rem[nx] || csiz[nx] > csiz[ret]) continue;
			if(csiz[nx] > sta/2){
				found = 0;
				ret = nx;
				break;
			}
		}
	}
	return ret;
}

void DIST(int nw, int par, int wei, int dep){
	dist[nw][dep] = wei;
	for(auto ed : adj[nw]){
		int nx = ed.fi.fi;
		if(rem[nx] || nx==par) continue;
		DIST(nx, nw, wei+ed.fi.se, dep);
	}
}
void build(int nw, int pa, int DEP){
	// cout << " masuk\n";
	int cen = find(nw);
	// cout << cen << " cen\n";
	rem[cen] = 1; cdep[cen] = DEP; cpar[cen] = pa;

	DIST(cen, -1, 0, cdep[cen]);
	for(auto ed : adj[cen]){
		int nx = ed.fi.fi;
		if(rem[nx]) continue;
		build(nx, cen, DEP+1);
	}
}

bool vis[MAXN];
void UPD(int nw){
	int sta = nw;
	for(int i=cdep[sta]; i>=1; i--){
		val[nw] = min(val[nw], dist[sta][i]);
		nw = cpar[nw];
	}
}
int QUE(int nw){
	int ret = INF;
	int sta = nw;
	for(int i=cdep[sta]; i>=1; i--){
		if(vis[nw]) ret = min(ret, dist[sta][i]+val[nw]);
		nw = cpar[nw];
	}
	return ret;
}
void ANS(int nw, int par){
	for(auto ed : adj[nw]){
		int nx = ed.fi.fi;
		if(nx == par) continue;
		ANS(nx, nw);
	}
	if(type[nw]) UPD(nw);
	vis[nw] = 1;
	// cout << nw << " upd\n";
	for(auto in : cari[nw]){
		int idx = IDX[in], sta = STA[in];
		ans[in] = QUE(sta);
		// cout << in << ' '<< sta << " idx\n";
	}
}
signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> s >> q >> e;
	for(int i=1; i<=n-1; i++){
		cin >> u[i] >> v[i] >> w[i];
		adj[u[i]].pb({{v[i], w[i]}, i});
		adj[v[i]].pb({{u[i], w[i]}, i});
	}
	dfs(e, 0);
	for(int i=1; i<=s; i++){
		int x; cin >> x;
		type[x] = 1;
	}

	build(e, 0, 1);
	// cout << "p\n";
	for(int i=1; i<=n; i++){
		val[i] = INF;
	}
	// for(int i=1; i<=n; i++){
	// 	cout << "i"<< i  << " \n";
	// 	for(int j=1; j<=3; j++) cout << dist[i][j] << ' ';
	// 		cout << '\n';
	// }

	for(int i=1; i<=n-1; i++){
		if(cdep[u[i]] < cdep[v[i]]) cchi[i] = v[i]; // v di bawah
		else cchi[i] = u[i];
	}
	for(int XX=1; XX<=q; XX++){
		int idx, sta; cin >> idx >> sta;
		IDX[XX] = idx; STA[XX] = sta;
		int node = chi[idx]; // upd child dari edge
		A.upd(in[node], 1); A.upd(out[node], -1);

		if(A.que(in[sta]) == 0){ // masi bisa ke root
			ans[XX] = -1;
			// cout << "escaped\n";
		} else {
			// cari ans nya
			// cout << cchi[idx] << ' ' << XX << " xx\n";
			cari[cchi[idx]].pb(XX); // dep dr node bawah dr edge idx
		}
		A.upd(in[node], -1); A.upd(out[node], 1);
	}
	// sort dr paling bawah

	ANS(e, -1);

	for(int i=1; i<=q; i++){
		if(ans[i] == -1) cout << "escaped\n";
		else if(ans[i] >= INF) cout << "oo\n";
		else cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

valley.cpp: In function 'void ANS(long long int, long long int)':
valley.cpp:129:7: warning: unused variable 'idx' [-Wunused-variable]
  129 |   int idx = IDX[in], sta = STA[in];
      |       ^~~

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