oj.uz

답안 #77080

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77080 2018-09-20T17:14:51 Z zetapi Evacuation plan (IZhO18_plan) C++14
0 / 100
 765 ms 88532 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=wei[X];
	while(X!=Y)
	{
		X=Parent[X][0];
		res=min(res,wei[X]);
	}
	return res;
	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=2;A<=N;A++)
		assert(Parent[A][0]!=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:163:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<edge.size();A++)
              ~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 9848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 391 ms 63024 KB Output is correct
2 Correct 692 ms 86332 KB Output is correct
3 Correct 705 ms 86448 KB Output is correct
4 Correct 238 ms 57272 KB Output is correct
5 Correct 741 ms 86428 KB Output is correct
6 Correct 733 ms 86444 KB Output is correct
7 Correct 724 ms 86480 KB Output is correct
8 Correct 716 ms 86428 KB Output is correct
9 Correct 765 ms 86464 KB Output is correct
10 Correct 714 ms 86476 KB Output is correct
11 Correct 731 ms 86456 KB Output is correct
12 Correct 712 ms 86364 KB Output is correct
13 Correct 730 ms 86436 KB Output is correct
14 Correct 718 ms 86480 KB Output is correct
15 Correct 742 ms 88532 KB Output is correct
16 Correct 714 ms 86472 KB Output is correct
17 Correct 704 ms 86412 KB Output is correct
18 Correct 717 ms 86556 KB Output is correct
19 Incorrect 221 ms 58788 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -