Submission #545538

#	Time	Username	Problem	Language	Result	Execution time	Memory
545538		MilosMilutinovic	Valley (BOI19_valley)	C++14	100 / 100	274 ms	118836 KiB

valley

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}

const ll inf=1e18;
int n,s,q,e,x[100005],y[100005],w[100005],id[100005],is[100005];
int root[100005],tsz,ls[5000005],rs[5000005],dfn[100005],dfo[100005],T;
ll dep[100005],st[5000005],lzy[5000005];
vector<pii> adj[100005];

void build(int&c,int l,int r){
	c=++tsz;
	if(l==r)return (void)(st[c]=(is[id[l]]?dep[id[l]]:inf));
	int m=(l+r)/2;
	build(ls[c],l,m);
	build(rs[c],m+1,r);
	st[c]=min(st[ls[c]],st[rs[c]]);
}

void modify(int p,int&c,int l,int r,int tl,int tr,int v){
	if(tl>tr||l>tr||r<tl) return;
	c=++tsz; ls[c]=ls[p]; rs[c]=rs[p]; st[c]=st[p]; lzy[c]=lzy[p];
	if(tl<=l&&r<=tr){st[c]+=v; lzy[c]+=v; return;}
	int m=(l+r)/2;
	modify(ls[p],ls[c],l,m,tl,tr,v);
	modify(rs[p],rs[c],m+1,r,tl,tr,v);
	st[c]=min(st[ls[c]],st[rs[c]])+lzy[c];
}

ll query(int c,int l,int r,int tl,int tr){
	if(tl>tr||l>tr||r<tl) return inf;
	if(tl<=l&&r<=tr) return st[c];
	int m=(l+r)/2;
	return min(query(ls[c],l,m,tl,tr),query(rs[c],m+1,r,tl,tr))+lzy[c];
}

void dfs0(int u,int p){
	dfn[u]=++T,id[T]=u;
	for(auto e:adj[u]) if(e.fi!=p) dep[e.fi]=dep[u]+e.se,dfs0(e.fi,u);
	dfo[u]=T;
}
void dfs1(int u,int p,int wu){
	if(p!=0) modify(root[p],root[u],1,T,dfn[u],dfo[u],-2*wu);
	for(auto e:adj[u]) if(e.fi!=p) dfs1(e.fi,u,e.se);
}

bool anc(int u,int v){return dfn[u]<=dfn[v]&&dfo[v]<=dfo[u];}

void deb(int c,int l,int r){
	printf("st:%d %d %d %d %d\n",c,l,r,ls[c],rs[c]);
	if(l==r){printf("%lld ",st[c]); return;}
	int m=(l+r)/2;
	deb(ls[c],l,m);
	deb(rs[c],m+1,r);
}

int main(){
	scanf("%d%d%d%d",&n,&s,&q,&e);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x[i],&y[i],&w[i]);
		adj[x[i]].pb(mp(y[i],w[i]));
		adj[y[i]].pb(mp(x[i],w[i]));
	}
	for(int i=1,r;i<=s;i++) scanf("%d",&r),is[r]=1;
	dfs0(1,0); build(root[1],1,T); dfs1(1,0,0);
	//deb(root[1],1,T);
	while(q--){
		int i,r;scanf("%d%d",&i,&r);
		int u=x[i],v=y[i];
		if(dep[u]>dep[v]) swap(u,v);
		if(anc(v,e)==anc(v,r)){printf("escaped\n"); continue;}
		ll ans=dep[r];
		if(anc(v,r)) ans+=query(root[r],1,T,dfn[v],dfo[v]);
		else ans+=min(query(root[r],1,T,1,dfn[v]-1),query(root[r],1,T,dfo[v]+1,T));
		if(ans>=1e17) printf("oo\n");
		else printf("%lld\n",ans);
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d%d%d%d",&n,&s,&q,&e);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d%d%d",&x[i],&y[i],&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:77:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  for(int i=1,r;i<=s;i++) scanf("%d",&r),is[r]=1;
      |                          ~~~~~^~~~~~~~~
valley.cpp:81:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   int i,r;scanf("%d%d",&i,&r);
      |           ~~~~~^~~~~~~~~~~~~~

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