oj.uz

Submission #77076

# Submission time Handle Problem Language Result Execution time Memory
77076 2018-09-20T16:39:14 Z zetapi Evacuation plan (IZhO18_plan) C++14
0 / 100
 770 ms 88644 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define int long long
#define itr iterator
 
typedef pair<int,int> pii;
 
const int MAX=2e5;
const int INF=1e12;
 
vector<pair<int,pii>> edge;
 
vector<pii> adj[MAX];
vector<int> vec[MAX];
 
int N,M,K,Q,X,Y,Z,arr[MAX],wei[MAX],hei[MAX],Value[MAX][20],Parent[MAX][20];
int par[MAX],rank_[MAX];
 
void init()
{
	for(int A=1;A<=N;A++)
	{
		par[A]=A;
		rank_[A]=0;
	}
	return ;
}
 
int root(int X)
{
	if(par[X]==X)
		return X;
	return par[X]=root(par[X]);
}
 
void unions(int X,int Y)
{
	int u=root(X),v=root(Y);
	if(u==v)
		return ;
	vec[X].pb(Y);
	vec[Y].pb(X);
	if(rank_[u]<rank_[v])
		par[u]=v;
	else if(rank_[v]<rank_[u])
		par[v]=u;
	else
	{
		par[u]=v;
		rank_[v]++;
	}
	return ;
}
 
void dfs(int node,int par)
{
	assert(Parent[node][0]==0);
	Parent[node][0]=par;
	Value[node][0]=min(wei[node],wei[par]);
	assert(Value[node][0]!=INF);
	for(auto A:vec[node])
	{
		if(A==par)
			continue;
		hei[A]=hei[node]+1;
		dfs(A,node);
	}
	return ;
}
 
void dijkstra()
{
	int vis[MAX];
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int A=0;A<=N;A++)
	{
		vis[A]=0;
		wei[A]=INF;
	}
	for(int A=1;A<=K;A++)
	{
		wei[arr[A]]=0;
		pq.push(mp(0,arr[A]));
	}
	while(!pq.empty())
	{
		pii cur=pq.top();
		pq.pop();
		if(vis[cur.second])
			continue;
		vis[cur.second]=1;
		for(auto A:adj[cur.second])
		{
			if(A.second+cur.first<wei[A.first])
			{
				wei[A.first]=A.second+cur.first;
				pq.push(mp(wei[A.first],A.first));
			}
		}
	}
	return ;
}
 
int lca(int X,int Y)
{
	if(hei[X]>hei[Y])
		swap(X,Y);
	int dis=hei[Y]-hei[X];
	for(int A=19;A>=0;A--)
		if(dis&(1<<A))
			dis-=(1<<A),
			Y=Parent[Y][A];
	assert(dis==0);
	assert(hei[X]==hei[Y]);
	for(int A=19;A>=0;A--)
		if(Parent[X][A]!=Parent[Y][A])
			X=Parent[X][A],
			Y=Parent[Y][A];
	return Parent[X][0];
}
 
int query(int X,int Y)
{
	int res=INF;
	for(int A=19;A>=0;A--)
	{
		if(hei[Parent[X][A]]>=hei[Y])
		{
			res=min(res,Value[X][A]);
			X=Parent[X][A];
		}
	}
	return res;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
 
	cin>>N>>M;
	for(int A=1;A<=M;A++)
	{
		cin>>X>>Y>>Z;
		adj[X].pb(mp(Y,Z));
		adj[Y].pb(mp(X,Z));
		edge.pb(mp(Z,mp(X,Y)));
	}
	cin>>K;
	for(int A=1;A<=K;A++)
		cin>>arr[A];
	dijkstra();
	/*for(int A=1;A<=N;A++)
		cout<<"shortest distance for node "<<A<<" is "<<wei[A]<<"\n";*/
	for(int A=0;A<edge.size();A++)
		edge[A].first=min(wei[edge[A].second.first],wei[edge[A].second.second]);
	sort(edge.begin(),edge.end());
	reverse(edge.begin(),edge.end());
	init();
	for(auto A:edge)
		unions(A.second.first,A.second.second);
	dfs(1,0);
	for(int A=0;A<20;A++)
		Value[0][A]=INF;
	for(int A=1;A<20;A++)
	{
		for(int B=1;B<=N;B++)
		{
			Parent[B][A]=Parent[Parent[B][A-1]][A-1];
			Value[B][A]=min(Value[B][A-1],Value[Parent[B][A-1]][A-1]);
		}
	}
	cin>>Q;
	while(Q--)
	{
		cin>>X>>Y;
		int cur=lca(X,Y);
		cout<<min(query(X,cur),query(Y,cur))<<"\n";
	}
	return 0;
}

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:157:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<edge.size();A++)
              ~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 63056 KB Output is correct
2 Correct 718 ms 86484 KB Output is correct
3 Correct 728 ms 86536 KB Output is correct
4 Correct 243 ms 57252 KB Output is correct
5 Correct 723 ms 86304 KB Output is correct
6 Correct 731 ms 86388 KB Output is correct
7 Correct 718 ms 86448 KB Output is correct
8 Correct 742 ms 86336 KB Output is correct
9 Correct 708 ms 86356 KB Output is correct
10 Correct 742 ms 86356 KB Output is correct
11 Correct 711 ms 86364 KB Output is correct
12 Correct 711 ms 86356 KB Output is correct
13 Correct 719 ms 86516 KB Output is correct
14 Correct 724 ms 86468 KB Output is correct
15 Correct 770 ms 88644 KB Output is correct
16 Correct 757 ms 86456 KB Output is correct
17 Correct 708 ms 86444 KB Output is correct
18 Correct 702 ms 86396 KB Output is correct
19 Incorrect 218 ms 58836 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -