Submission #704591

#	Time	Username	Problem	Language	Result	Execution time	Memory
704591		hoangnghiep	Valley (BOI19_valley)	C++14	100 / 100	284 ms	68488 KiB

valley

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define repeat(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define p push
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
//#define DEBUG
//#define multipletest
using namespace std;
const int LIM=1e5;
const int mod=1e9+7;
const int maxn=20;
const int inf=1e18;
int n,m,x,y,k,t,e,q,s;
int dx[8]={1,-1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,1,-1,1,-1};
char c;
int a[LIM+5],factorial[(1<<maxn)+5],inv_fact[(1<<maxn)+5];
bool notprime[LIM+5];
vector<pii> adj[LIM+5];
map<int,int> mp;
char grid[100+5][100+5];
int power(int a,int b){
   if(b==0) return 1;
    int t=power(a,b/2);
    t = t * t %mod;
    if(b%2==1) t = t * a %mod;
    return t;
}
bool check(int x,int y){
    if(x<=0 || x>n || y<=0 || y>m || grid[x][y]=='T'){
   return false;
     }
    return true;
}
class DSU{
	int *parent;
	int *rank;
	int *tot;
	public:
	DSU(int n){
		rank=new int[n+5];
		parent=new int[n+5];
		tot=new int [n+5];
		for(int i=0;i<n+5;i++){
			parent[i]=i;
			rank[i]=0;
			tot[i]=1;
		}
	}
	int find(int i){
		if(parent[i]==i){
			return i;
		}
		return parent[i]=find(parent[i]);
	}
	void unite(int u,int v){
		int i=find(u);
		int j=find(v);
		if(i!=j){
			if(rank[i]>rank[j]){
				parent[j]=i;
				tot[i]+=tot[j];
			}
			else if(rank[i]<rank[j]){
				parent[i]=j;
				tot[j]+=tot[i];
			}
			else{
				parent[j]=i;
				rank[i]++;
				tot[i]+=tot[j];
			}
		}
	}
	int total(int u){
	   return tot[u];
	}
};
void precal(int n){
	factorial[0]=1;
	inv_fact[0]=1;
    for (int i = 1; i <n; ++i)
	{
		factorial[i] = factorial[i - 1] * i % mod;
		inv_fact[i] = inv_fact[i - 1] * power(i, mod - 2) % mod;
	}
}
int choose(int n,int k){
	if(k<0 || k>n) return 0;
	return factorial[n] * inv_fact[n-k] % mod * inv_fact[k] %mod;
}
void Sieve(){
	notprime[0]=notprime[1]=true;
    for(int i=2;i<LIM+5;++i){
    	if(notprime[i]==false){
    	for(int j=i*i;j<LIM+5;j+=i){
    		notprime[j]=true;
		}
    }
	}
}
bool shop[LIM+5];
int tail[LIM+5];
int depth[LIM+5],disc[LIM+5],dp[LIM+5],low[LIM+5];
int up[20][LIM+5];
int updist[20][LIM+5];
int upshop[20][LIM+5];
pii edges[LIM+5];
int timedfs=0;
void dfs(int u,int parent){
	disc[u]=++timedfs;
	up[0][u]=parent;
	for(auto to:adj[u]){
		if(to.f!=parent){
		int v=to.f;
		int w=to.s;
		depth[v]=depth[u]+1;
		dfs(v,u);
		updist[0][v]=w;
		dp[u]=min(dp[u],(dp[v]==inf?inf:dp[v]+w));
	  }
	}
	tail[u]=timedfs;
}
void solve(){
//Sieve();
//   precal();
    cin>>n>>s>>q>>e;
    for(int i=1;i<=n-1;++i){
    	int u,v,w;
    	cin>>u>>v>>w;
    	adj[u].push_back({v,w});
    	adj[v].push_back({u,w});
    	edges[i].f=u,edges[i].s=v;
	}
	for(int i=1;i<=n;++i){
		dp[i]=inf;
	}
	for(int i=0;i<s;++i){
		int u;
		cin>>u;
		dp[u]=0;
   }
	dfs(e,e);
	for(int i=0;i<20;++i){
		upshop[i][e]=dp[e];
	}
	for(int i=1;i<=n;++i){
	    upshop[0][i]=dp[i];
	}
// 	cout<<dp[e]<<endl;
	for(int i=1;i<20;++i){
		for(int j=1;j<=n;++j){
			up[i][j]=up[i-1][up[i-1][j]];
			updist[i][j]=updist[i-1][j] + updist[i-1][up[i-1][j]];
			upshop[i][j]=min(upshop[i-1][j],updist[i-1][j] + upshop[i-1][up[i-1][j]] );
		}
	}
// 			for(int i=1;i<20;++i){
// 		for(int j=1;j<=n;++j){
// 	 		cout<<upshop[i][j] <<" ";
// 	 } 
// 	 cout<<endl;
// 	}
	while(q--){
		int id,vertex;
		cin>>id>>vertex;
		int u=edges[id].f,v=edges[id].s;
//		cout<<depth[u]<<" "<<depth[v]<<endl;
		if(depth[u]>depth[v]){
			swap(u,v);
		}
		if(disc[v]<=disc[vertex] && tail[v]>=tail[vertex]){
			int ans=inf;
            int jump= depth[vertex]-depth[u];
            int temp=0,path=0;
            while(jump>0){
            	 if(jump%2==1){
            	 	ans  = min(ans , (upshop[temp][vertex]==inf?inf : path + upshop[temp][vertex]));
            	 	path+=updist[temp][vertex];
            	 	vertex = up[temp][vertex];
				 }
				 jump>>=1;
				 temp++;
			}
			if(ans==inf) cout<<"oo"<<endl;
			else cout<<ans<<endl;
		}
		else{
			cout<<"escaped"<<endl;
		}
	}
}
signed main(){
  // freopen(".inp","r",stdin);
  // freopen(".out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int test;
	test=1;
	#ifdef multipletest
	cin>>test;
	#endif
	while(test--){
        solve();
        #ifdef DEBUG
		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
	    #endif
	}
}

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