oj.uz

Submission #499099

# Submission time Handle Problem Language Result Execution time Memory
499099 2021-12-27T08:38:44 Z beksultan04 Evacuation plan (IZhO18_plan) C++14
100 / 100
 951 ms 126468 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define pii pair<int,int>
#define ret return
#define fr first
#define sc second
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define nosol puts("-1");
#define pb push_back
#define endi puts("");
#define ordered_set tree <int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N = 1e6+12,INF = 1e18+7;
int dis[N],a[N],used[N],ans[N];
vector <pii> g[N];
set <int> s[N];
struct dsu{
	int n;
	vector<int> p;
	dsu(int N) : n(N), p(N+1) {
		for (int i=0;i<=n;++i){
			p[i] = i;
		}
	}
	
	int find_baty(int x){
		if (x == p[x])ret x;
		ret p[x] = find_baty(p[x]);
	}
	
	void merge(int a,int b,int dl){
		a = find_baty(a);
		b = find_baty(b);
		if (a == b)ret ;
		if (s[a].size() > s[b].size())swap(s[a],s[b]);
		for (auto x:s[a]){
			if (s[b].count(x)){
				ans[x] = dl;
			}
			else {
				s[b].insert(x);
			}
		}
		p[a] = b;
	}
	
	
};

bool cmp(int a,int b){
	ret dis[a]<dis[b];
}
main(){
	int n,i,m;
	cin>>n>>m;
	dsu ds(n);
	for (i=1;i<=m;++i){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].pb({y,z});
		g[y].pb({x,z});
	}
	int qq;
	cin>>qq;
	priority_queue <pii> ss;
	for (i=1;i<=n;++i)dis[i] = INF;
	for (i=0;i<qq;++i){
		int x;
		cin>>x;
		ss.push({0,x});
		dis[x] = 0;
	}
	while (!ss.empty()){
		int x = ss.top().sc;
		ss.pop();
		for (auto [to,c]:g[x]){
			if (dis[to] > dis[x] +c){
				dis[to] = dis[x]+c;
				ss.push({-dis[x],to});
			}
		}
	}
	cin>>qq;
	for (i=1;i<=qq;++i){
		int x,y;
		cin>>x>>y;
		s[x].insert(i);
		s[y].insert(i);
	} 
	vector <pii> v;
	for (i=1;i<=n;++i)
		v.pb({dis[i],i});
	sort(allr(v));
	for (auto [dl,x]: v){
		
		used[x] = 1;
		for (auto [to,asd]: g[x]){
			if (used[to]){
				ds.merge(x,to,dl);
			}
		}
		
	}
	
	for (i=1;i<=qq;++i){
		cout <<ans[i]<<" ";
	}
	
	
}

Compilation message

plan.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main(){
      | ^~~~
plan.cpp: In function 'int main()':
plan.cpp:83:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   for (auto [to,c]:g[x]){
      |             ^
plan.cpp:101:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |  for (auto [dl,x]: v){
      |            ^
plan.cpp:104:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |   for (auto [to,asd]: g[x]){
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70688 KB Output is correct
2 Correct 33 ms 70968 KB Output is correct
3 Correct 33 ms 70860 KB Output is correct
4 Correct 31 ms 70768 KB Output is correct
5 Correct 35 ms 70932 KB Output is correct
6 Correct 39 ms 70940 KB Output is correct
7 Correct 31 ms 70732 KB Output is correct
8 Correct 31 ms 70796 KB Output is correct
9 Correct 33 ms 71116 KB Output is correct
10 Correct 34 ms 70988 KB Output is correct
11 Correct 34 ms 71024 KB Output is correct
12 Correct 33 ms 70984 KB Output is correct
13 Correct 32 ms 70984 KB Output is correct
14 Correct 33 ms 70988 KB Output is correct
15 Correct 33 ms 70948 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70688 KB Output is correct
2 Correct 33 ms 70968 KB Output is correct
3 Correct 33 ms 70860 KB Output is correct
4 Correct 31 ms 70768 KB Output is correct
5 Correct 35 ms 70932 KB Output is correct
6 Correct 39 ms 70940 KB Output is correct
7 Correct 31 ms 70732 KB Output is correct
8 Correct 31 ms 70796 KB Output is correct
9 Correct 33 ms 71116 KB Output is correct
10 Correct 34 ms 70988 KB Output is correct
11 Correct 34 ms 71024 KB Output is correct
12 Correct 33 ms 70984 KB Output is correct
13 Correct 32 ms 70984 KB Output is correct
14 Correct 33 ms 70988 KB Output is correct
15 Correct 33 ms 70948 KB Output is correct
16 Correct 375 ms 98804 KB Output is correct
17 Correct 918 ms 125328 KB Output is correct
18 Correct 89 ms 75768 KB Output is correct
19 Correct 294 ms 94608 KB Output is correct
20 Correct 904 ms 125420 KB Output is correct
21 Correct 536 ms 107856 KB Output is correct
22 Correct 322 ms 98156 KB Output is correct
23 Correct 918 ms 125268 KB Output is correct
24 Correct 918 ms 125376 KB Output is correct
25 Correct 911 ms 125592 KB Output is correct
26 Correct 354 ms 100900 KB Output is correct
27 Correct 379 ms 102596 KB Output is correct
28 Correct 296 ms 94316 KB Output is correct
29 Correct 293 ms 94404 KB Output is correct
30 Correct 288 ms 94520 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70732 KB Output is correct
2 Correct 34 ms 70784 KB Output is correct
3 Correct 33 ms 70732 KB Output is correct
4 Correct 33 ms 70764 KB Output is correct
5 Correct 33 ms 70688 KB Output is correct
6 Correct 32 ms 70768 KB Output is correct
7 Correct 32 ms 70752 KB Output is correct
8 Correct 33 ms 70756 KB Output is correct
9 Correct 32 ms 70688 KB Output is correct
10 Correct 32 ms 70660 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 86592 KB Output is correct
2 Correct 651 ms 105108 KB Output is correct
3 Correct 669 ms 105280 KB Output is correct
4 Correct 137 ms 79380 KB Output is correct
5 Correct 658 ms 105288 KB Output is correct
6 Correct 644 ms 105180 KB Output is correct
7 Correct 643 ms 105156 KB Output is correct
8 Correct 653 ms 105224 KB Output is correct
9 Correct 657 ms 105080 KB Output is correct
10 Correct 642 ms 105184 KB Output is correct
11 Correct 642 ms 105152 KB Output is correct
12 Correct 657 ms 105212 KB Output is correct
13 Correct 654 ms 105144 KB Output is correct
14 Correct 646 ms 105532 KB Output is correct
15 Correct 657 ms 105356 KB Output is correct
16 Correct 662 ms 105352 KB Output is correct
17 Correct 647 ms 105132 KB Output is correct
18 Correct 687 ms 105216 KB Output is correct
19 Correct 138 ms 79440 KB Output is correct
20 Correct 664 ms 105264 KB Output is correct
21 Correct 587 ms 102708 KB Output is correct
22 Correct 157 ms 81716 KB Output is correct
23 Correct 146 ms 79800 KB Output is correct
24 Correct 152 ms 81612 KB Output is correct
25 Correct 148 ms 81580 KB Output is correct
26 Correct 165 ms 80064 KB Output is correct
27 Correct 135 ms 79388 KB Output is correct
28 Correct 149 ms 81560 KB Output is correct
29 Correct 141 ms 79404 KB Output is correct
30 Correct 217 ms 87728 KB Output is correct
31 Correct 136 ms 79452 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70688 KB Output is correct
2 Correct 33 ms 70968 KB Output is correct
3 Correct 33 ms 70860 KB Output is correct
4 Correct 31 ms 70768 KB Output is correct
5 Correct 35 ms 70932 KB Output is correct
6 Correct 39 ms 70940 KB Output is correct
7 Correct 31 ms 70732 KB Output is correct
8 Correct 31 ms 70796 KB Output is correct
9 Correct 33 ms 71116 KB Output is correct
10 Correct 34 ms 70988 KB Output is correct
11 Correct 34 ms 71024 KB Output is correct
12 Correct 33 ms 70984 KB Output is correct
13 Correct 32 ms 70984 KB Output is correct
14 Correct 33 ms 70988 KB Output is correct
15 Correct 33 ms 70948 KB Output is correct
16 Correct 375 ms 98804 KB Output is correct
17 Correct 918 ms 125328 KB Output is correct
18 Correct 89 ms 75768 KB Output is correct
19 Correct 294 ms 94608 KB Output is correct
20 Correct 904 ms 125420 KB Output is correct
21 Correct 536 ms 107856 KB Output is correct
22 Correct 322 ms 98156 KB Output is correct
23 Correct 918 ms 125268 KB Output is correct
24 Correct 918 ms 125376 KB Output is correct
25 Correct 911 ms 125592 KB Output is correct
26 Correct 354 ms 100900 KB Output is correct
27 Correct 379 ms 102596 KB Output is correct
28 Correct 296 ms 94316 KB Output is correct
29 Correct 293 ms 94404 KB Output is correct
30 Correct 288 ms 94520 KB Output is correct
31 Correct 31 ms 70732 KB Output is correct
32 Correct 34 ms 70784 KB Output is correct
33 Correct 33 ms 70732 KB Output is correct
34 Correct 33 ms 70764 KB Output is correct
35 Correct 33 ms 70688 KB Output is correct
36 Correct 32 ms 70768 KB Output is correct
37 Correct 32 ms 70752 KB Output is correct
38 Correct 33 ms 70756 KB Output is correct
39 Correct 32 ms 70688 KB Output is correct
40 Correct 32 ms 70660 KB Output is correct
41 Correct 308 ms 86592 KB Output is correct
42 Correct 651 ms 105108 KB Output is correct
43 Correct 669 ms 105280 KB Output is correct
44 Correct 137 ms 79380 KB Output is correct
45 Correct 658 ms 105288 KB Output is correct
46 Correct 644 ms 105180 KB Output is correct
47 Correct 643 ms 105156 KB Output is correct
48 Correct 653 ms 105224 KB Output is correct
49 Correct 657 ms 105080 KB Output is correct
50 Correct 642 ms 105184 KB Output is correct
51 Correct 642 ms 105152 KB Output is correct
52 Correct 657 ms 105212 KB Output is correct
53 Correct 654 ms 105144 KB Output is correct
54 Correct 646 ms 105532 KB Output is correct
55 Correct 657 ms 105356 KB Output is correct
56 Correct 662 ms 105352 KB Output is correct
57 Correct 647 ms 105132 KB Output is correct
58 Correct 687 ms 105216 KB Output is correct
59 Correct 138 ms 79440 KB Output is correct
60 Correct 664 ms 105264 KB Output is correct
61 Correct 587 ms 102708 KB Output is correct
62 Correct 157 ms 81716 KB Output is correct
63 Correct 146 ms 79800 KB Output is correct
64 Correct 152 ms 81612 KB Output is correct
65 Correct 148 ms 81580 KB Output is correct
66 Correct 165 ms 80064 KB Output is correct
67 Correct 135 ms 79388 KB Output is correct
68 Correct 149 ms 81560 KB Output is correct
69 Correct 141 ms 79404 KB Output is correct
70 Correct 217 ms 87728 KB Output is correct
71 Correct 136 ms 79452 KB Output is correct
72 Correct 587 ms 108940 KB Output is correct
73 Correct 906 ms 125704 KB Output is correct
74 Correct 951 ms 125744 KB Output is correct
75 Correct 903 ms 125644 KB Output is correct
76 Correct 921 ms 125632 KB Output is correct
77 Correct 912 ms 125668 KB Output is correct
78 Correct 910 ms 125672 KB Output is correct
79 Correct 905 ms 125940 KB Output is correct
80 Correct 919 ms 125640 KB Output is correct
81 Correct 921 ms 125572 KB Output is correct
82 Correct 917 ms 125696 KB Output is correct
83 Correct 948 ms 125700 KB Output is correct
84 Correct 906 ms 125704 KB Output is correct
85 Correct 924 ms 125824 KB Output is correct
86 Correct 931 ms 125708 KB Output is correct
87 Correct 931 ms 125632 KB Output is correct
88 Correct 915 ms 125592 KB Output is correct
89 Correct 334 ms 97976 KB Output is correct
90 Correct 932 ms 125652 KB Output is correct
91 Correct 853 ms 124380 KB Output is correct
92 Correct 373 ms 100544 KB Output is correct
93 Correct 425 ms 124036 KB Output is correct
94 Correct 375 ms 100464 KB Output is correct
95 Correct 399 ms 102068 KB Output is correct
96 Correct 473 ms 126468 KB Output is correct
97 Correct 379 ms 101064 KB Output is correct
98 Correct 354 ms 98872 KB Output is correct
99 Correct 371 ms 101064 KB Output is correct
100 Correct 350 ms 99136 KB Output is correct