Submission #1368546

#TimeUsernameProblemLanguageResultExecution timeMemory
1368546ivazivaValley (BOI19_valley)C++20
100 / 100
311 ms53668 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100001
#define MAXM 20
#define int long long 

int n,s,q,e;
vector<pair<int,pair<int,int>>> edges;
vector<pair<int,int>> adj[MAXN];
vector<int> shops;
int parent[MAXM][MAXN];
int tin[MAXN],tout[MAXN];
int dist[MAXN],dist1[MAXN];
int seg[MAXN*4],magic[MAXM][MAXN];
int timer=1;

void dfs(int node,int pret)
{
	tin[node]=timer;timer++;parent[0][node]=pret;
	for (pair<int,int> edge:adj[node])
	{
		if (edge.first==pret) continue;
		dist[edge.first]=dist[node]+edge.second;
		dist1[edge.first]=dist1[node]+1;
		dfs(edge.first,node);
	}
	tout[node]=timer-1;
}

int jump(int node,int k)
{
	for (int bit=0;bit<MAXM;bit++)
	{
		if (k&(1<<bit)) node=parent[bit][node];
	}
	return node;
}

int lca(int node1,int node2)
{
	if (dist1[node1]<dist1[node2]) swap(node1,node2);
	node1=jump(node1,dist1[node1]-dist1[node2]);
	if (node1==node2) return node1;
	for (int bit=MAXM-1;bit>=0;bit--)
	{
		if (parent[bit][node1]!=parent[bit][node2])
		{
			node1=parent[bit][node1];
			node2=parent[bit][node2];
		}
	}
	return parent[0][node1];
}

void update(int node,int l,int r,int pos,int val)
{
	if (l==r) seg[node]=val;
	else
	{
		int mid=(l+r)/2;
		if (pos<=mid) update(2*node,l,mid,pos,val);
		else update(2*node+1,mid+1,r,pos,val);
		seg[node]=min(seg[2*node],seg[2*node+1]);
	}
}

int query(int node,int l,int r,int a,int b)
{
	if (a>b) return LLONG_MAX;
	if (l==a and r==b) return seg[node];
	int mid=(l+r)/2;
	return min(query(2*node,l,mid,a,min(b,mid)),query(2*node+1,mid+1,r,max(a,mid+1),b));
}

int32_t main()
{
	cin>>n>>s>>q>>e;edges.push_back({0,{0,0}});
	for (int i=1;i<n;i++) 
	{
		int u,v,w;cin>>u>>v>>w;
		edges.push_back({w,{u,v}});
		adj[u].push_back({v,w});adj[v].push_back({u,w});
	}
	for (int i=1;i<=s;i++) {int x;cin>>x;shops.push_back(x);}
	dfs(e,0);for (int i=0;i<4*MAXN;i++) seg[i]=LLONG_MAX;
	for (int shop:shops) update(1,1,n,tin[shop],dist[shop]);
	for (int node=1;node<=n;node++)
	{
		int value=query(1,1,n,tin[node],tout[node]);
		if (value==LLONG_MAX) magic[0][node]=LLONG_MAX;
		else magic[0][node]=value-2*dist[node];
	}
	for (int bit=1;bit<MAXM;bit++)
	{
		for (int node=1;node<=n;node++) parent[bit][node]=parent[bit-1][parent[bit-1][node]];
		for (int node=1;node<=n;node++) magic[bit][node]=min(magic[bit-1][node],magic[bit-1][parent[bit-1][node]]);
	}
	for (int i=1;i<=q;i++)
	{
		int edge,city;cin>>edge>>city;
		int node1=edges[edge].second.first,node2=edges[edge].second.second;
		if (!(lca(city,node1)==node1 and lca(city,node2)==node2)) {cout<<"escaped"<<endl;continue;}
		if (dist1[node1]<dist1[node2]) swap(node1,node2);
		int distanca=dist1[city]-dist1[node1]+1;int answer=LLONG_MAX;int city1=city;
		for (int bit=MAXM-1;bit>=0;bit--)
		{
			if (distanca&(1<<bit)) {answer=min(answer,magic[bit][city1]);city1=parent[bit][city1];}
		}
		if (answer!=LLONG_MAX) cout<<answer+dist[city]<<endl;
		else cout<<"oo"<<endl;
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...