oj.uz

Submission #134686

# Submission time Handle Problem Language Result Execution time Memory
134686 2019-07-23T07:26:44 Z FedericoS Evacuation plan (IZhO18_plan) C++14
100 / 100
 1517 ms 29488 KB 
#include <iostream>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef pair<int,int> pii;

int c=0;
int N,M;
int x,y,z;
vector<pii> grafo[100005];
priority_queue<pii> PQ;
int D[100005];
bool V[100005];
vector<pair<int,pii>> E;
int P[100005];
int H[100005];
int W[100005];
vector<int> albero[100005];

int fi(int x){
	while(x!=P[x])
		x=P[x];
	return x;
}

void un(int x, int y, int v){

	x=fi(x);
	y=fi(y);

	if(H[x]<H[y])
		swap(x,y);

	W[y]=v;
	P[y]=x;
	H[x]=max(H[x],H[y]+1);
}

void DFS(int k, int p=-1, int h=0){
	H[k]=h;
	for(int f:albero[k])
		if(f!=p)
			DFS(f,k,h+1);
}

int LCA(int x, int y){

	if(x==y)
		return D[x];

	if(H[y]>H[x])
		swap(x,y);

	while(H[x]-1>H[y])
		x=P[x];

	if(P[x]==y)
		return W[x];
	if(H[x]!=H[y])
		x=P[x];

	assert(H[x]==H[y]);

	while(P[x]!=P[y]){
		x=P[x];
		y=P[y];
	}

	return min(W[x],W[y]);

}

int main(){
	cin>>N>>M;
	for(int i=0;i<M;i++){
		cin>>x>>y>>z;
		x--,y--;
		grafo[x].push_back({y,z});
		grafo[y].push_back({x,z});
	}

	for(int i=0;i<N;i++)
		D[i]=1e9;

	cin>>M;
	for(int i=0;i<M;i++){
		cin>>x;
		x--;
		PQ.push({0,x});
		D[x]=0;
	}

	while(!PQ.empty()){

		x=PQ.top().second;
		PQ.pop();

		if(V[x])
			continue;
		V[x]=true;

		for(pii f:grafo[x])
			if(D[f.first]>D[x]+f.second){
				D[f.first]=D[x]+f.second;
				PQ.push({-D[f.first],f.first});
			}
	}

	for(int i=0;i<N;i++)
		for(pii f:grafo[i])
			if(f.first>i)
				E.push_back({min(D[i],D[f.first]),{i,f.first}});
	sort(E.begin(),E.end(),greater<pair<int,pii>>());

	for(int i=0;i<N;i++)
		P[i]=i;

	for(auto q:E){
		pii p=q.second;
		if(fi(p.first)!=fi(p.second))
			un(p.first,p.second,q.first);
	}

	for(int i=0;i<N;i++)
		if(i!=P[i])
			albero[P[i]].push_back(i);
		else
			M=i;
	DFS(M);

	cin>>M;
	for(int i=0;i<M;i++){
		cin>>x>>y;
		x--,y--;
		cout<<LCA(x,y)<<endl;
	}

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 11 ms 5176 KB Output is correct
3 Correct 11 ms 5112 KB Output is correct
4 Correct 6 ms 5032 KB Output is correct
5 Correct 11 ms 5112 KB Output is correct
6 Correct 11 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 4984 KB Output is correct
9 Correct 11 ms 5112 KB Output is correct
10 Correct 11 ms 5112 KB Output is correct
11 Correct 11 ms 5116 KB Output is correct
12 Correct 11 ms 5112 KB Output is correct
13 Correct 11 ms 5112 KB Output is correct
14 Correct 11 ms 5112 KB Output is correct
15 Correct 11 ms 5112 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 11 ms 5176 KB Output is correct
3 Correct 11 ms 5112 KB Output is correct
4 Correct 6 ms 5032 KB Output is correct
5 Correct 11 ms 5112 KB Output is correct
6 Correct 11 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 4984 KB Output is correct
9 Correct 11 ms 5112 KB Output is correct
10 Correct 11 ms 5112 KB Output is correct
11 Correct 11 ms 5116 KB Output is correct
12 Correct 11 ms 5112 KB Output is correct
13 Correct 11 ms 5112 KB Output is correct
14 Correct 11 ms 5112 KB Output is correct
15 Correct 11 ms 5112 KB Output is correct
16 Correct 613 ms 12332 KB Output is correct
17 Correct 1470 ms 28848 KB Output is correct
18 Correct 118 ms 7376 KB Output is correct
19 Correct 598 ms 14024 KB Output is correct
20 Correct 1501 ms 29040 KB Output is correct
21 Correct 858 ms 17300 KB Output is correct
22 Correct 593 ms 12760 KB Output is correct
23 Correct 1484 ms 28880 KB Output is correct
24 Correct 1466 ms 28860 KB Output is correct
25 Correct 1482 ms 28952 KB Output is correct
26 Correct 594 ms 13776 KB Output is correct
27 Correct 597 ms 13864 KB Output is correct
28 Correct 595 ms 13772 KB Output is correct
29 Correct 594 ms 13848 KB Output is correct
30 Correct 606 ms 13988 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4988 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 16764 KB Output is correct
2 Correct 1091 ms 28492 KB Output is correct
3 Correct 1103 ms 28376 KB Output is correct
4 Correct 205 ms 11752 KB Output is correct
5 Correct 1094 ms 28468 KB Output is correct
6 Correct 1093 ms 28528 KB Output is correct
7 Correct 1075 ms 28520 KB Output is correct
8 Correct 1083 ms 28524 KB Output is correct
9 Correct 1086 ms 28432 KB Output is correct
10 Correct 1091 ms 28600 KB Output is correct
11 Correct 1098 ms 28516 KB Output is correct
12 Correct 1098 ms 28404 KB Output is correct
13 Correct 1092 ms 28476 KB Output is correct
14 Correct 1096 ms 28420 KB Output is correct
15 Correct 1096 ms 29208 KB Output is correct
16 Correct 1085 ms 28440 KB Output is correct
17 Correct 1094 ms 28380 KB Output is correct
18 Correct 1096 ms 28476 KB Output is correct
19 Correct 203 ms 11880 KB Output is correct
20 Correct 1089 ms 28388 KB Output is correct
21 Correct 1069 ms 28176 KB Output is correct
22 Correct 234 ms 13416 KB Output is correct
23 Correct 224 ms 12404 KB Output is correct
24 Correct 217 ms 13512 KB Output is correct
25 Correct 218 ms 13416 KB Output is correct
26 Correct 228 ms 12624 KB Output is correct
27 Correct 204 ms 11848 KB Output is correct
28 Correct 216 ms 13416 KB Output is correct
29 Correct 206 ms 11624 KB Output is correct
30 Correct 222 ms 13564 KB Output is correct
31 Correct 210 ms 11880 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 11 ms 5176 KB Output is correct
3 Correct 11 ms 5112 KB Output is correct
4 Correct 6 ms 5032 KB Output is correct
5 Correct 11 ms 5112 KB Output is correct
6 Correct 11 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 4984 KB Output is correct
9 Correct 11 ms 5112 KB Output is correct
10 Correct 11 ms 5112 KB Output is correct
11 Correct 11 ms 5116 KB Output is correct
12 Correct 11 ms 5112 KB Output is correct
13 Correct 11 ms 5112 KB Output is correct
14 Correct 11 ms 5112 KB Output is correct
15 Correct 11 ms 5112 KB Output is correct
16 Correct 613 ms 12332 KB Output is correct
17 Correct 1470 ms 28848 KB Output is correct
18 Correct 118 ms 7376 KB Output is correct
19 Correct 598 ms 14024 KB Output is correct
20 Correct 1501 ms 29040 KB Output is correct
21 Correct 858 ms 17300 KB Output is correct
22 Correct 593 ms 12760 KB Output is correct
23 Correct 1484 ms 28880 KB Output is correct
24 Correct 1466 ms 28860 KB Output is correct
25 Correct 1482 ms 28952 KB Output is correct
26 Correct 594 ms 13776 KB Output is correct
27 Correct 597 ms 13864 KB Output is correct
28 Correct 595 ms 13772 KB Output is correct
29 Correct 594 ms 13848 KB Output is correct
30 Correct 606 ms 13988 KB Output is correct
31 Correct 6 ms 5112 KB Output is correct
32 Correct 6 ms 4984 KB Output is correct
33 Correct 6 ms 5112 KB Output is correct
34 Correct 6 ms 4984 KB Output is correct
35 Correct 6 ms 4984 KB Output is correct
36 Correct 6 ms 4984 KB Output is correct
37 Correct 6 ms 4988 KB Output is correct
38 Correct 6 ms 4984 KB Output is correct
39 Correct 6 ms 5112 KB Output is correct
40 Correct 6 ms 4984 KB Output is correct
41 Correct 456 ms 16764 KB Output is correct
42 Correct 1091 ms 28492 KB Output is correct
43 Correct 1103 ms 28376 KB Output is correct
44 Correct 205 ms 11752 KB Output is correct
45 Correct 1094 ms 28468 KB Output is correct
46 Correct 1093 ms 28528 KB Output is correct
47 Correct 1075 ms 28520 KB Output is correct
48 Correct 1083 ms 28524 KB Output is correct
49 Correct 1086 ms 28432 KB Output is correct
50 Correct 1091 ms 28600 KB Output is correct
51 Correct 1098 ms 28516 KB Output is correct
52 Correct 1098 ms 28404 KB Output is correct
53 Correct 1092 ms 28476 KB Output is correct
54 Correct 1096 ms 28420 KB Output is correct
55 Correct 1096 ms 29208 KB Output is correct
56 Correct 1085 ms 28440 KB Output is correct
57 Correct 1094 ms 28380 KB Output is correct
58 Correct 1096 ms 28476 KB Output is correct
59 Correct 203 ms 11880 KB Output is correct
60 Correct 1089 ms 28388 KB Output is correct
61 Correct 1069 ms 28176 KB Output is correct
62 Correct 234 ms 13416 KB Output is correct
63 Correct 224 ms 12404 KB Output is correct
64 Correct 217 ms 13512 KB Output is correct
65 Correct 218 ms 13416 KB Output is correct
66 Correct 228 ms 12624 KB Output is correct
67 Correct 204 ms 11848 KB Output is correct
68 Correct 216 ms 13416 KB Output is correct
69 Correct 206 ms 11624 KB Output is correct
70 Correct 222 ms 13564 KB Output is correct
71 Correct 210 ms 11880 KB Output is correct
72 Correct 836 ms 17468 KB Output is correct
73 Correct 1477 ms 28840 KB Output is correct
74 Correct 1468 ms 29008 KB Output is correct
75 Correct 1488 ms 29064 KB Output is correct
76 Correct 1478 ms 28892 KB Output is correct
77 Correct 1458 ms 28916 KB Output is correct
78 Correct 1466 ms 28860 KB Output is correct
79 Correct 1467 ms 28820 KB Output is correct
80 Correct 1498 ms 29052 KB Output is correct
81 Correct 1479 ms 28956 KB Output is correct
82 Correct 1474 ms 28980 KB Output is correct
83 Correct 1481 ms 28848 KB Output is correct
84 Correct 1470 ms 28844 KB Output is correct
85 Correct 1495 ms 29488 KB Output is correct
86 Correct 1517 ms 28872 KB Output is correct
87 Correct 1480 ms 28852 KB Output is correct
88 Correct 1504 ms 28852 KB Output is correct
89 Correct 597 ms 12808 KB Output is correct
90 Correct 1473 ms 28968 KB Output is correct
91 Correct 1466 ms 28392 KB Output is correct
92 Correct 604 ms 13768 KB Output is correct
93 Correct 613 ms 13236 KB Output is correct
94 Correct 603 ms 13756 KB Output is correct
95 Correct 609 ms 13852 KB Output is correct
96 Correct 626 ms 12780 KB Output is correct
97 Correct 601 ms 12392 KB Output is correct
98 Correct 607 ms 13720 KB Output is correct
99 Correct 593 ms 12240 KB Output is correct
100 Correct 601 ms 13844 KB Output is correct