Submission #196893

#	Time	Username	Problem	Language	Result	Execution time	Memory
196893		arnold518	Valley (BOI19_valley)	C++14	23 / 100	588 ms	45356 KiB

valley

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5;
const ll INF = 1e15;

struct Edge { int u, v, w; };

int N, S, Q, E;
vector<pii> adj[MAXN+10];
Edge edge[MAXN+10];
int C[MAXN+10];

int L[MAXN+10], R[MAXN+10], pos[MAXN+10], cnt;

bool reach(int I, int u, int v)
{
	bool a=(L[edge[I].v]<=L[u] && L[u]<=R[edge[I].v]);
	bool b=(L[edge[I].v]<=L[v] && L[v]<=R[edge[I].v]);
	return a==b;
}

void dfs(int now, int bef)
{
	L[now]=R[now]=++cnt;
	pos[L[now]]=now;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now);
		R[now]=max(R[now], R[nxt.first]);
	}
}

int sz[MAXN+10], cenpar[MAXN+10], cendep[MAXN+10];
ll dist[MAXN+10][30];
pll D1[MAXN+10], D2[MAXN+10];
bool del[MAXN+10];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		getsz(nxt.first, now);
		sz[now]+=sz[nxt.first];
	}
}

int getcen(int now, int bef, int S)
{
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(sz[nxt.first]>S/2) return getcen(nxt.first, now, S);
	}	
	return now;
}

pll dfs2(int now, int bef, ll depth, int root, int cdep)
{
	dist[now][cdep]=depth;
	pll ret={INF, INF};
	if(C[now]) ret=min(ret, {depth, root});
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		ret=min(ret, dfs2(nxt.first, now, depth+nxt.second, root, cdep));
	}
	return ret;
}

int decomp(int now, int bef, int dep)
{
	getsz(now, now);
	now=getcen(now, now, sz[now]);
	del[now]=true;
	cendep[now]=dep;

	if(bef) cenpar[now]=bef;
	else cenpar[now]=now;

	D1[now]={INF, INF};
	D2[now]={INF, INF};

	for(auto nxt : adj[now])
	{
		if(del[nxt.first]) continue;
		int nxtcen=decomp(nxt.first, now, dep+1);

		pll t=dfs2(nxt.first, now, nxt.second, nxtcen, dep);
		if(t<D1[now]) D2[now]=D1[now], D1[now]=t;
		else if(t<D2[now]) D2[now]=t;
	}

	//printf("%d : %lld %lld / %lld %lld\n", now, D1[now].first, D1[now].second, D2[now].first, D2[now].second);

	del[now]=false;
	return now;
}

ll query(int now, int cut)
{
	ll ans=INF;
	int bef=now, beg=now;
	while(1)
	{
		if(reach(cut, beg, now))
		{
			if(D1[now].second!=bef) ans=min(ans, D1[now].first+dist[beg][cendep[now]]);
			else ans=min(ans, D2[now].first+dist[beg][cendep[now]]);
			if(C[now]) ans=min(ans, dist[beg][cendep[now]]);
		}
		if(now==cenpar[now]) break;
		bef=now;
		now=cenpar[now];
	}
	return ans;
}

int main()
{
	int i, j;

	scanf("%d%d%d%d", &N, &S, &Q, &E);
	for(i=1; i<N; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		edge[i]={u, v, w};
	}

	for(i=1; i<=S; i++)
	{
		int t;
		scanf("%d", &t);
		C[t]=1;
	}

	dfs(E, E);
	for(i=1; i<N; i++) if(L[edge[i].u]>L[edge[i].v]) swap(edge[i].u, edge[i].v);

	decomp(1, 0, 0);

	while(Q--)
	{
		int A, B;
		scanf("%d%d", &A, &B);

		if(reach(A, E, B)) { printf("escaped\n"); continue; }
		ll t=query(B, A);
		if(t==INF) printf("oo\n");
		else printf("%lld\n", t);
	}
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:131:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
valley.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &S, &Q, &E);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
valley.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A, &B);
   ~~~~~^~~~~~~~~~~~~~~~

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