oj.uz

Submission #467797

# Submission time Handle Problem Language Result Execution time Memory
467797 2021-08-24T13:53:17 Z keta_tsimakuridze Evacuation plan (IZhO18_plan) C++14
100 / 100
 1132 ms 64228 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int par[N],p[N][20],w[N],n,m,k,Lg = 18,tmin[N],timer,tmout[N],d[N];
vector<pair<int,pii> > edges;
vector<pii> V[N],e;
vector<int> child[N],comp[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
void merge(int u,int v,int W) {
	u = par[u];
	v = par[v];
	if(v == u) return;
	if(comp[u].size() < comp[v].size()) swap(u,v);
	for(int i=0; i < comp[v].size();i++) {
		comp[u].push_back(comp[v][i]);
		par[comp[v][i]] = u;
	}
	p[v][0] = u;
	w[v] = W;
	child[u].push_back(v);
	
}
void dfs(int u) {
	tmin[u] = ++timer;
	for(int j = 1; j <= Lg; j++) p[u][j] = p[p[u][j-1]][j-1];
	for(int i=0;i<child[u].size();i++) {
		p[child[u][i]][0] = u;
		dfs(child[u][i]);
	}
	tmout[u] = ++timer;
}
bool check(int u,int v) {
	if(tmin[u] <= tmin[v] && tmout[u] >= tmout[v]) return 1;
	return 0;
}
int find_lca(int u,int v) {
	if(check(u,v)) return u;
	if(check(v,u)) return v;
	
	for(int j=Lg;j>=0;j--) {
		if(p[u][j] && !check(p[u][j],v)) u = p[u][j];
	}	
	return p[u][0];
} 
int get(int u,int v) {
	int ans = mod;
	if(v == u) return ans;
	for(int j=Lg;j>=0;j--) {
		if(p[u][j] && !check(p[u][j],v)) u = p[u][j];
	}		
	return w[u];
}
main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++) {
		int u,v,w;
		cin >> u >> v >> w;
		V[u].push_back({v,w});
		V[v].push_back({u,w});
		e.push_back({u,v});
	}
	for(int i=1;i<=n;i++) d[i] = mod,par[i] = i, comp[i].push_back(i);
	cin >> k;
	for(int i=1;i<=k;i++) {
		int a;
		cin >> a;
		d[a] = 0;
		q.push({0,a});
	}
	
	while(q.size()) {
		int u = q.top().s;
		int dist = q.top().f;
		q.pop(); 
		if(d[u] < dist) continue;
		for(int i=0;i<V[u].size();i++) {
			int v = V[u][i].f;
			if(d[v] > d[u] + V[u][i].s) {
				d[v] = d[u] + V[u][i].s;
				q.push({d[v],v});
			}
		}
	}
	for(int i = 0; i < e.size(); i++) {
		edges.push_back({min(d[e[i].f],d[e[i].s]),{e[i].f,e[i].s}});
	}
	sort(edges.rbegin(),edges.rend());
	for(int i = 0; i < edges.size(); i++) {
		merge(edges[i].s.f,edges[i].s.s,edges[i].f);
	}
	dfs(par[1]);
	int q;
	cin >> q;
	while(q--) {
		int u,v;
		cin >> u >> v;
		int lca = find_lca(u,v);
		cout<<min(get(u,lca),get(v,lca))<<endl;
	}
 }

Compilation message

plan.cpp: In function 'void merge(int, int, int)':
plan.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0; i < comp[v].size();i++) {
      |               ~~^~~~~~~~~~~~~~~~
plan.cpp: In function 'void dfs(int)':
plan.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=0;i<child[u].size();i++) {
      |              ~^~~~~~~~~~~~~~~~
plan.cpp: At global scope:
plan.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~
plan.cpp: In function 'int main()':
plan.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i=0;i<V[u].size();i++) {
      |               ~^~~~~~~~~~~~
plan.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 0; i < e.size(); i++) {
      |                 ~~^~~~~~~~~~
plan.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0; i < edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 12 ms 14656 KB Output is correct
3 Correct 12 ms 14540 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 12 ms 14656 KB Output is correct
6 Correct 12 ms 14656 KB Output is correct
7 Correct 9 ms 14408 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 12 ms 14664 KB Output is correct
10 Correct 12 ms 14668 KB Output is correct
11 Correct 12 ms 14540 KB Output is correct
12 Correct 12 ms 14656 KB Output is correct
13 Correct 12 ms 14564 KB Output is correct
14 Correct 12 ms 14540 KB Output is correct
15 Correct 12 ms 14540 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 12 ms 14656 KB Output is correct
3 Correct 12 ms 14540 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 12 ms 14656 KB Output is correct
6 Correct 12 ms 14656 KB Output is correct
7 Correct 9 ms 14408 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 12 ms 14664 KB Output is correct
10 Correct 12 ms 14668 KB Output is correct
11 Correct 12 ms 14540 KB Output is correct
12 Correct 12 ms 14656 KB Output is correct
13 Correct 12 ms 14564 KB Output is correct
14 Correct 12 ms 14540 KB Output is correct
15 Correct 12 ms 14540 KB Output is correct
16 Correct 469 ms 34788 KB Output is correct
17 Correct 1093 ms 63848 KB Output is correct
18 Correct 89 ms 19128 KB Output is correct
19 Correct 439 ms 38596 KB Output is correct
20 Correct 1116 ms 63848 KB Output is correct
21 Correct 670 ms 44324 KB Output is correct
22 Correct 457 ms 37420 KB Output is correct
23 Correct 1113 ms 64032 KB Output is correct
24 Correct 1120 ms 64012 KB Output is correct
25 Correct 1109 ms 63892 KB Output is correct
26 Correct 451 ms 38332 KB Output is correct
27 Correct 460 ms 38336 KB Output is correct
28 Correct 435 ms 38396 KB Output is correct
29 Correct 442 ms 38320 KB Output is correct
30 Correct 462 ms 38520 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14340 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14432 KB Output is correct
6 Correct 10 ms 14396 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 9 ms 14400 KB Output is correct
9 Correct 9 ms 14396 KB Output is correct
10 Correct 9 ms 14412 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 39544 KB Output is correct
2 Correct 818 ms 54308 KB Output is correct
3 Correct 838 ms 54296 KB Output is correct
4 Correct 190 ms 34496 KB Output is correct
5 Correct 820 ms 54264 KB Output is correct
6 Correct 812 ms 54240 KB Output is correct
7 Correct 832 ms 54324 KB Output is correct
8 Correct 838 ms 54252 KB Output is correct
9 Correct 828 ms 54464 KB Output is correct
10 Correct 817 ms 54296 KB Output is correct
11 Correct 815 ms 54312 KB Output is correct
12 Correct 856 ms 54300 KB Output is correct
13 Correct 841 ms 54272 KB Output is correct
14 Correct 798 ms 54300 KB Output is correct
15 Correct 824 ms 54564 KB Output is correct
16 Correct 871 ms 54268 KB Output is correct
17 Correct 832 ms 54304 KB Output is correct
18 Correct 811 ms 54512 KB Output is correct
19 Correct 183 ms 33948 KB Output is correct
20 Correct 815 ms 54264 KB Output is correct
21 Correct 801 ms 53988 KB Output is correct
22 Correct 191 ms 35512 KB Output is correct
23 Correct 218 ms 35768 KB Output is correct
24 Correct 193 ms 35368 KB Output is correct
25 Correct 184 ms 35268 KB Output is correct
26 Correct 221 ms 36652 KB Output is correct
27 Correct 199 ms 34484 KB Output is correct
28 Correct 182 ms 35404 KB Output is correct
29 Correct 195 ms 34436 KB Output is correct
30 Correct 184 ms 35496 KB Output is correct
31 Correct 194 ms 34500 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 12 ms 14656 KB Output is correct
3 Correct 12 ms 14540 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 12 ms 14656 KB Output is correct
6 Correct 12 ms 14656 KB Output is correct
7 Correct 9 ms 14408 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 12 ms 14664 KB Output is correct
10 Correct 12 ms 14668 KB Output is correct
11 Correct 12 ms 14540 KB Output is correct
12 Correct 12 ms 14656 KB Output is correct
13 Correct 12 ms 14564 KB Output is correct
14 Correct 12 ms 14540 KB Output is correct
15 Correct 12 ms 14540 KB Output is correct
16 Correct 469 ms 34788 KB Output is correct
17 Correct 1093 ms 63848 KB Output is correct
18 Correct 89 ms 19128 KB Output is correct
19 Correct 439 ms 38596 KB Output is correct
20 Correct 1116 ms 63848 KB Output is correct
21 Correct 670 ms 44324 KB Output is correct
22 Correct 457 ms 37420 KB Output is correct
23 Correct 1113 ms 64032 KB Output is correct
24 Correct 1120 ms 64012 KB Output is correct
25 Correct 1109 ms 63892 KB Output is correct
26 Correct 451 ms 38332 KB Output is correct
27 Correct 460 ms 38336 KB Output is correct
28 Correct 435 ms 38396 KB Output is correct
29 Correct 442 ms 38320 KB Output is correct
30 Correct 462 ms 38520 KB Output is correct
31 Correct 9 ms 14412 KB Output is correct
32 Correct 8 ms 14340 KB Output is correct
33 Correct 8 ms 14412 KB Output is correct
34 Correct 9 ms 14412 KB Output is correct
35 Correct 9 ms 14432 KB Output is correct
36 Correct 10 ms 14396 KB Output is correct
37 Correct 9 ms 14412 KB Output is correct
38 Correct 9 ms 14400 KB Output is correct
39 Correct 9 ms 14396 KB Output is correct
40 Correct 9 ms 14412 KB Output is correct
41 Correct 378 ms 39544 KB Output is correct
42 Correct 818 ms 54308 KB Output is correct
43 Correct 838 ms 54296 KB Output is correct
44 Correct 190 ms 34496 KB Output is correct
45 Correct 820 ms 54264 KB Output is correct
46 Correct 812 ms 54240 KB Output is correct
47 Correct 832 ms 54324 KB Output is correct
48 Correct 838 ms 54252 KB Output is correct
49 Correct 828 ms 54464 KB Output is correct
50 Correct 817 ms 54296 KB Output is correct
51 Correct 815 ms 54312 KB Output is correct
52 Correct 856 ms 54300 KB Output is correct
53 Correct 841 ms 54272 KB Output is correct
54 Correct 798 ms 54300 KB Output is correct
55 Correct 824 ms 54564 KB Output is correct
56 Correct 871 ms 54268 KB Output is correct
57 Correct 832 ms 54304 KB Output is correct
58 Correct 811 ms 54512 KB Output is correct
59 Correct 183 ms 33948 KB Output is correct
60 Correct 815 ms 54264 KB Output is correct
61 Correct 801 ms 53988 KB Output is correct
62 Correct 191 ms 35512 KB Output is correct
63 Correct 218 ms 35768 KB Output is correct
64 Correct 193 ms 35368 KB Output is correct
65 Correct 184 ms 35268 KB Output is correct
66 Correct 221 ms 36652 KB Output is correct
67 Correct 199 ms 34484 KB Output is correct
68 Correct 182 ms 35404 KB Output is correct
69 Correct 195 ms 34436 KB Output is correct
70 Correct 184 ms 35496 KB Output is correct
71 Correct 194 ms 34500 KB Output is correct
72 Correct 676 ms 44368 KB Output is correct
73 Correct 1070 ms 63800 KB Output is correct
74 Correct 1132 ms 63768 KB Output is correct
75 Correct 1077 ms 63720 KB Output is correct
76 Correct 1068 ms 63768 KB Output is correct
77 Correct 1096 ms 63796 KB Output is correct
78 Correct 1084 ms 63784 KB Output is correct
79 Correct 1117 ms 63932 KB Output is correct
80 Correct 1108 ms 63712 KB Output is correct
81 Correct 1116 ms 63744 KB Output is correct
82 Correct 1112 ms 63708 KB Output is correct
83 Correct 1112 ms 63748 KB Output is correct
84 Correct 1117 ms 63816 KB Output is correct
85 Correct 1091 ms 64228 KB Output is correct
86 Correct 1090 ms 63784 KB Output is correct
87 Correct 1090 ms 63928 KB Output is correct
88 Correct 1093 ms 63772 KB Output is correct
89 Correct 440 ms 37428 KB Output is correct
90 Correct 1071 ms 63728 KB Output is correct
91 Correct 1076 ms 63876 KB Output is correct
92 Correct 442 ms 38376 KB Output is correct
93 Correct 485 ms 39264 KB Output is correct
94 Correct 442 ms 38228 KB Output is correct
95 Correct 438 ms 38428 KB Output is correct
96 Correct 509 ms 39820 KB Output is correct
97 Correct 459 ms 37432 KB Output is correct
98 Correct 442 ms 38304 KB Output is correct
99 Correct 461 ms 37416 KB Output is correct
100 Correct 458 ms 38388 KB Output is correct