Submission #898489

#	Time	Username	Problem	Language	Result	Execution time	Memory
898489		Mathias	Valley (BOI19_valley)	C++14	23 / 100	154 ms	63136 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
const int MAXN = 1e5+7;
const int LOG = 18;
struct str{
	ll fi,sc,th;
};
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;
int w,diff,cnt=0;
void DFS(int x,int f,int d){
	pre[x]=++cnt;
	depth[x]=depth[f]+1;
	suma[x]=suma[f]+d;
	jp[x][0]={f,dis[f],f};
	for(int i=1;i<LOG;i++){
		jp[x][i].fi=jp[jp[x][i-1].fi][i-1].fi;
		if(jp[jp[x][i-1].fi][i-1].sc>jp[x][i-1].sc){
			jp[x][i].sc=jp[x][i-1].sc;
			jp[x][i].th=jp[x][i-1].th;
		}
		else{
			jp[x][i].sc=jp[jp[x][i-1].fi][i-1].sc;
			jp[x][i].th=jp[jp[x][i-1].fi][i-1].th;
		}
	}
	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(int 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,mini=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(int i=1;i<=n;i++){
		if(degree[i]==1 and i!=r) que.push(i); 
		dis[i]=INF;	
	} 
	for(int i=1;i<=s;i++){
		cin>>sk;
		dis[sk]=0;
	}
	for(int i=1;i<=n;i++) visited[i]=0;
	DFS1(r,0);
	//for(int i=1;i<=n;i++) cout<<wo[i]<<' '<<ojciec[i]<<'\n'; cout<<'\n';
	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);
	//for(int i=1;i<=n;i++) cout<<dis[i]<<' '; cout<<'\n';
	while(q--){
		cin>>a>>b;
		x=in[a].first;
		y=in[a].second;
		if(depth[x]>depth[y]) swap(x,y);
		//cout<<y<<' '<<b<<'\n';
		if(anc(y,b)==false){
			cout<<"escaped\n";
			continue;
		}
		b1=b;
		diff=depth[y]-depth[b];
		mini=dis[b];
		w=b;
		for(int i=LOG-1;i>=0;i--){
			if(depth[jp[b][i].fi]<depth[y]) continue;
			if(jp[b][i].sc<mini){
				mini=jp[b][i].sc;
				w=jp[b][i].th;
			}
			b=jp[b][i].fi;
		}
		if(mini==INF) cout<<"oo\n";
		else cout<<suma[b1]-suma[w]+mini<<'\n';
	}
	return 0;
}

Compilation message (stderr)

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

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