Submission #712815

#	Time	Username	Problem	Language	Result	Execution time	Memory
712815		TimDee	Valley (BOI19_valley)	C++17	100 / 100	194 ms	29196 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,popcnt")

#define int long long
#define forn(i,n) for(size_t i=0;i<n;++i)
#define pb push_back
#define all(x)  x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second

const int inf=1e18;
const int N=1e5;
int sz[N],d[N],par[N],top[N],ind[N],rind[N];
int dist[N],dp[N];
int shop[N];

int z=0;
vector<pi> adj[N];
pi e[N];
int W[N];

struct sgt {
	vector<int> t;
	int sz;
	sgt(int n) {
		sz=1; 
		while(sz<n) sz<<=1; 
		t.assign(2*sz,inf);
	}
	void upd(int v, int l, int r, int i) {
		if (r-l==1) return;
		int m=(l+r)>>1;
		if (i<m) upd(2*v+1,l,m,i);
		else upd(2*v+2,m,r,i);
		t[v]=min(t[2*v+1],t[2*v+2]);
	}
	void set(int i, int x) {
		t[sz-1+i]=x;
		upd(0,0,sz,i);
	}
	int q(int v, int l, int r, int lx, int rx) {
		if (rx<=l || r<=lx) return inf;
		if (lx<=l && r<=rx) return t[v];
		int m=(l+r)>>1;
		int lq=q(2*v+1,l,m,lx,rx);
		int rq=q(2*v+2,m,r,lx,rx);
		return min(lq,rq);
	}
	int q(int l, int r) {
		if (l>=r) return inf;
		return q(0,0,sz,l,r);
	}
};
sgt st(N);

void dfs(int u, int p) {
	sz[u]=1;
	dp[u]=shop[u]?0:inf;
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p) continue;
		d[v]=d[u]+1;
		dist[v]=dist[u]+w;
		par[v]=u;
		dfs(v,u);
		sz[u]+=sz[v];
		dp[u]=min(dp[v]+w,dp[u]);
	}
}
void dfs(int u, int p, int t) {
	top[u]=t;
	rind[z]=u;
	ind[u]=z++;
	st.set(ind[u],(dp[u]==inf)?inf:(dp[u]-dist[u]));
	int mx=-1;
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p) continue;
		if (mx==-1) mx=v;
		if (sz[v]>sz[mx]) mx=v;
	}
	if (mx==-1) return;
	dfs(mx,u,t);
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p || v==mx) continue;
		dfs(v,u,v);
	}
}

int lca(int u, int v) {
	while (top[u]!=top[v]) {
		if (d[top[u]]<d[top[v]]) swap(u,v);
		u=par[top[u]];
	}
	return (d[u]<d[v])?u:v;
}

int query(int u, int v) {
	int ret=inf;
	while (top[u]!=top[v]) {
		int q=st.q(ind[top[u]],ind[u]+1);
		ret=min(ret,q);
		u=par[top[u]];
	}
	int q=st.q(ind[v],ind[u]+1);
	return min(ret,q);
}

void solve() {

	int n,s,q,E; cin>>n>>s>>q>>E; --E;
	forn(i,n-1) {
		int u,v,w; cin>>u>>v>>w; --u,--v;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
		e[i]={u,v};
		W[i]=w;
	}
	forn(i,s) {
		int u; cin>>u; --u; shop[u]=1;
	}
	dfs(E,-1);
	dfs(E,-1,E);
	//forn(i,n) cout<<dp[i]<<' '; cout<<'\n';
	//forn(i,n) cout<<ind[i]<<' '; cout<<'\n';
	//forn(i,n) forn(j,n) if (j>=i) cout<<i<<' '<<j<<' '<<st.q(i,j+1)<<'\n';
	while (q--) {
		int i, x; cin>>i>>x; --i, --x;
		int u=e[i].f, v=e[i].s;
		if (par[u]==v) swap(u,v);
		if (lca(x,v)!=v) {
			cout<<"escaped\n";
			continue;
		}
		int z=query(x,v);
		if (z==inf) cout<<"oo\n";
		else cout<<z+dist[x]<<'\n';
	}

}
 
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t=1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int, long long int)':
valley.cpp:82:14: warning: unused variable 'w' [-Wunused-variable]
   82 |   int v=e.f, w=e.s;
      |              ^
valley.cpp:90:14: warning: unused variable 'w' [-Wunused-variable]
   90 |   int v=e.f, w=e.s;
      |              ^
valley.cpp: In function 'void solve()':
valley.cpp:9:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
    9 | #define forn(i,n) for(size_t i=0;i<n;++i)
......
  118 |  forn(i,n-1) {
      |       ~~~~~                        
valley.cpp:118:2: note: in expansion of macro 'forn'
  118 |  forn(i,n-1) {
      |  ^~~~
valley.cpp:9:35: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
    9 | #define forn(i,n) for(size_t i=0;i<n;++i)
      |                                   ^
valley.cpp:125:2: note: in expansion of macro 'forn'
  125 |  forn(i,s) {
      |  ^~~~

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