Submission #898550

#	Time	Username	Problem	Language	Result	Execution time	Memory
898550		Mathias	Valley (BOI19_valley)	C++14	100 / 100	147 ms	49452 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
const ll MAXN = 1e5+7;
const ll LOG = 18;
struct str{
	ll fi,sc;
};
int pre[MAXN];
int post[MAXN];
ll wo[MAXN];
int depth[MAXN];
int degree[MAXN];
int ojciec[MAXN];
ll dis[MAXN];
ll suma[MAXN];
bool visited[MAXN];
str jp[MAXN][LOG];
pair<int,int> in[MAXN];
vector<pair<int,ll> > g[MAXN];
queue<int> que;
ll w,diff,cnt=0;
void DFS(int x,int f,ll d){
	pre[x]=++cnt;
	depth[x]=depth[f]+1;
	suma[x]=suma[f]+d;
	jp[x][0]={f,min(dis[f]+wo[x],dis[x])};
	//cout<<jp[x][0].sc<<'\n';
	for(ll i=1;i<LOG;i++){
		jp[x][i].fi=jp[jp[x][i-1].fi][i-1].fi;
		jp[x][i].sc=min(jp[x][i-1].sc,jp[jp[x][i-1].fi][i-1].sc-suma[jp[x][i-1].fi]+suma[x]);
		//cout<<x<<' '<<i<<' '<<jp[x][i-1].sc<<' '<<jp[jp[x][i-1].fi][i-1].sc<<' '<<suma[jp[x][i-1].fi]<<' '<<suma[x]<<' '<<jp[x][i].sc<<'\n';
	}
	for(auto sas:g[x]){
		if(f==sas.first) continue;
		DFS(sas.first, x, sas.second);
	}
	post[x]=++cnt;
}
bool anc(int a,int b){
	return (pre[a] <= pre[b] && post[a] >= post[b]);
}
void DFS1(int x,int f){
	visited[x]=1;
	ojciec[x]=f;
	for(ll i=0;i<g[x].size();i++){
		if(g[x][i].first==f) wo[x]=g[x][i].second;
		if(!visited[g[x][i].first]){
			DFS1(g[x][i].first, x);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n,q,s,r,sk,a,b,x,y,b1,res=INF,c;
	cin>>n>>s>>q>>r;
	for(int i=1;i<n;i++){
		cin>>a>>b>>c;
		in[i]={a,b};
		g[a].push_back({b,c});
		g[b].push_back({a,c});
		degree[a]++;
		degree[b]++;
	}
	for(ll i=1;i<=n;i++){
		if(degree[i]==1 and i!=r) que.push(i); 
		dis[i]=INF;	
	} 
	for(ll i=1;i<=s;i++){
		cin>>sk;
		dis[sk]=0;
	}
	for(ll i=1;i<=n;i++) visited[i]=0;
	DFS1(r,0);
	while(!que.empty()){
		x=que.front();
		que.pop();
		dis[ojciec[x]]=min(dis[ojciec[x]], dis[x]+wo[x]);
		degree[ojciec[x]]--;
		if(degree[ojciec[x]]<=1 and ojciec[x]!=0) que.push(ojciec[x]);
	}
	DFS(r,r,0);
	while(q--){
		cin>>a>>b;
		x=in[a].first;
		y=in[a].second;
		if(depth[x]>depth[y]) swap(x,y);
		if(anc(y,b)==false){
			cout<<"escaped\n";
			continue;
		}
		res=dis[b];
		b1=b;
		for(int i=LOG-1;i>=0;i--){
			if(depth[jp[b][i].fi]<depth[y]) continue;
			if(jp[b][i].sc-suma[b]+suma[b1]<res){
				res=jp[b][i].sc-suma[b]+suma[b1];
			} 
			//cout<<b<<' '<<mini<<'\n';
			b=jp[b][i].fi;
		}
		if(res==INF) cout<<"oo\n";
		else cout<<res<<'\n';
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void DFS1(int, int)':
valley.cpp:47:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(ll i=0;i<g[x].size();i++){
      |             ~^~~~~~~~~~~~

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