oj.uz

Submission #77081

# Submission time Handle Problem Language Result Execution time Memory
77081 2018-09-20T17:16:49 Z zetapi Evacuation plan (IZhO18_plan) C++14
54 / 100
 4000 ms 89004 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]);
	while(X!=Y)
	{
		X=Parent[X][0];
		Y=Parent[Y][0];
	}
	return X;
}
 
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:164:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<edge.size();A++)
              ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 14 ms 10204 KB Output is correct
3 Correct 14 ms 10172 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 15 ms 10232 KB Output is correct
6 Correct 15 ms 10232 KB Output is correct
7 Correct 11 ms 9848 KB Output is correct
8 Correct 10 ms 9916 KB Output is correct
9 Correct 14 ms 10232 KB Output is correct
10 Correct 15 ms 10232 KB Output is correct
11 Correct 15 ms 10232 KB Output is correct
12 Correct 14 ms 10232 KB Output is correct
13 Correct 15 ms 10204 KB Output is correct
14 Correct 15 ms 10232 KB Output is correct
15 Correct 15 ms 10332 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 14 ms 10204 KB Output is correct
3 Correct 14 ms 10172 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 15 ms 10232 KB Output is correct
6 Correct 15 ms 10232 KB Output is correct
7 Correct 11 ms 9848 KB Output is correct
8 Correct 10 ms 9916 KB Output is correct
9 Correct 14 ms 10232 KB Output is correct
10 Correct 15 ms 10232 KB Output is correct
11 Correct 15 ms 10232 KB Output is correct
12 Correct 14 ms 10232 KB Output is correct
13 Correct 15 ms 10204 KB Output is correct
14 Correct 15 ms 10232 KB Output is correct
15 Correct 15 ms 10332 KB Output is correct
16 Correct 624 ms 47876 KB Output is correct
17 Correct 1198 ms 87008 KB Output is correct
18 Correct 91 ms 17704 KB Output is correct
19 Correct 508 ms 56452 KB Output is correct
20 Correct 1182 ms 86952 KB Output is correct
21 Correct 849 ms 64380 KB Output is correct
22 Correct 539 ms 60040 KB Output is correct
23 Correct 1207 ms 86928 KB Output is correct
24 Correct 1166 ms 86996 KB Output is correct
25 Correct 1202 ms 86928 KB Output is correct
26 Correct 508 ms 56328 KB Output is correct
27 Correct 522 ms 56332 KB Output is correct
28 Correct 513 ms 56360 KB Output is correct
29 Correct 511 ms 56380 KB Output is correct
30 Correct 504 ms 56460 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 11 ms 9848 KB Output is correct
6 Correct 10 ms 9720 KB Output is correct
7 Correct 11 ms 9720 KB Output is correct
8 Correct 10 ms 9720 KB Output is correct
9 Correct 10 ms 9848 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 62920 KB Output is correct
2 Correct 676 ms 86408 KB Output is correct
3 Correct 690 ms 86536 KB Output is correct
4 Correct 254 ms 57252 KB Output is correct
5 Correct 711 ms 86308 KB Output is correct
6 Correct 710 ms 86544 KB Output is correct
7 Correct 707 ms 86508 KB Output is correct
8 Correct 701 ms 86332 KB Output is correct
9 Correct 711 ms 86612 KB Output is correct
10 Correct 674 ms 86452 KB Output is correct
11 Correct 693 ms 86472 KB Output is correct
12 Correct 670 ms 86464 KB Output is correct
13 Correct 690 ms 86412 KB Output is correct
14 Correct 692 ms 86536 KB Output is correct
15 Correct 715 ms 88628 KB Output is correct
16 Correct 723 ms 86536 KB Output is correct
17 Correct 742 ms 86432 KB Output is correct
18 Correct 714 ms 86548 KB Output is correct
19 Correct 222 ms 58784 KB Output is correct
20 Correct 706 ms 86516 KB Output is correct
21 Correct 700 ms 86472 KB Output is correct
22 Correct 189 ms 55996 KB Output is correct
23 Correct 224 ms 56484 KB Output is correct
24 Correct 184 ms 56012 KB Output is correct
25 Correct 196 ms 55976 KB Output is correct
26 Correct 240 ms 56740 KB Output is correct
27 Correct 248 ms 58624 KB Output is correct
28 Correct 199 ms 56012 KB Output is correct
29 Correct 256 ms 57892 KB Output is correct
30 Correct 195 ms 56088 KB Output is correct
31 Correct 247 ms 57976 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 14 ms 10204 KB Output is correct
3 Correct 14 ms 10172 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 15 ms 10232 KB Output is correct
6 Correct 15 ms 10232 KB Output is correct
7 Correct 11 ms 9848 KB Output is correct
8 Correct 10 ms 9916 KB Output is correct
9 Correct 14 ms 10232 KB Output is correct
10 Correct 15 ms 10232 KB Output is correct
11 Correct 15 ms 10232 KB Output is correct
12 Correct 14 ms 10232 KB Output is correct
13 Correct 15 ms 10204 KB Output is correct
14 Correct 15 ms 10232 KB Output is correct
15 Correct 15 ms 10332 KB Output is correct
16 Correct 624 ms 47876 KB Output is correct
17 Correct 1198 ms 87008 KB Output is correct
18 Correct 91 ms 17704 KB Output is correct
19 Correct 508 ms 56452 KB Output is correct
20 Correct 1182 ms 86952 KB Output is correct
21 Correct 849 ms 64380 KB Output is correct
22 Correct 539 ms 60040 KB Output is correct
23 Correct 1207 ms 86928 KB Output is correct
24 Correct 1166 ms 86996 KB Output is correct
25 Correct 1202 ms 86928 KB Output is correct
26 Correct 508 ms 56328 KB Output is correct
27 Correct 522 ms 56332 KB Output is correct
28 Correct 513 ms 56360 KB Output is correct
29 Correct 511 ms 56380 KB Output is correct
30 Correct 504 ms 56460 KB Output is correct
31 Correct 10 ms 9720 KB Output is correct
32 Correct 11 ms 9720 KB Output is correct
33 Correct 11 ms 9720 KB Output is correct
34 Correct 10 ms 9720 KB Output is correct
35 Correct 11 ms 9848 KB Output is correct
36 Correct 10 ms 9720 KB Output is correct
37 Correct 11 ms 9720 KB Output is correct
38 Correct 10 ms 9720 KB Output is correct
39 Correct 10 ms 9848 KB Output is correct
40 Correct 10 ms 9720 KB Output is correct
41 Correct 365 ms 62920 KB Output is correct
42 Correct 676 ms 86408 KB Output is correct
43 Correct 690 ms 86536 KB Output is correct
44 Correct 254 ms 57252 KB Output is correct
45 Correct 711 ms 86308 KB Output is correct
46 Correct 710 ms 86544 KB Output is correct
47 Correct 707 ms 86508 KB Output is correct
48 Correct 701 ms 86332 KB Output is correct
49 Correct 711 ms 86612 KB Output is correct
50 Correct 674 ms 86452 KB Output is correct
51 Correct 693 ms 86472 KB Output is correct
52 Correct 670 ms 86464 KB Output is correct
53 Correct 690 ms 86412 KB Output is correct
54 Correct 692 ms 86536 KB Output is correct
55 Correct 715 ms 88628 KB Output is correct
56 Correct 723 ms 86536 KB Output is correct
57 Correct 742 ms 86432 KB Output is correct
58 Correct 714 ms 86548 KB Output is correct
59 Correct 222 ms 58784 KB Output is correct
60 Correct 706 ms 86516 KB Output is correct
61 Correct 700 ms 86472 KB Output is correct
62 Correct 189 ms 55996 KB Output is correct
63 Correct 224 ms 56484 KB Output is correct
64 Correct 184 ms 56012 KB Output is correct
65 Correct 196 ms 55976 KB Output is correct
66 Correct 240 ms 56740 KB Output is correct
67 Correct 248 ms 58624 KB Output is correct
68 Correct 199 ms 56012 KB Output is correct
69 Correct 256 ms 57892 KB Output is correct
70 Correct 195 ms 56088 KB Output is correct
71 Correct 247 ms 57976 KB Output is correct
72 Correct 950 ms 63512 KB Output is correct
73 Correct 1232 ms 86828 KB Output is correct
74 Correct 1239 ms 86816 KB Output is correct
75 Correct 1278 ms 86884 KB Output is correct
76 Correct 1228 ms 86780 KB Output is correct
77 Correct 1204 ms 86968 KB Output is correct
78 Correct 1213 ms 86808 KB Output is correct
79 Correct 1234 ms 86872 KB Output is correct
80 Correct 1172 ms 86944 KB Output is correct
81 Correct 1214 ms 86916 KB Output is correct
82 Correct 1255 ms 86852 KB Output is correct
83 Correct 1208 ms 86808 KB Output is correct
84 Correct 1194 ms 86876 KB Output is correct
85 Correct 1198 ms 89004 KB Output is correct
86 Correct 1248 ms 86928 KB Output is correct
87 Correct 1224 ms 86780 KB Output is correct
88 Correct 1220 ms 86852 KB Output is correct
89 Execution timed out 4024 ms 58264 KB Time limit exceeded
90 Halted 0 ms 0 KB -