oj.uz

Submission #898034

# Submission time Handle Problem Language Result Execution time Memory
898034 2024-01-04T08:31:21 Z penguin133 Evacuation plan (IZhO18_plan) C++17
100 / 100
 393 ms 80572 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, par[20][100005], mx[20][100005], dist[100005], dep[100005], vis[100005], pa[100005];
vector <pi> adj[100005];
vector <int> adj2[100005];
int P[100005];

int getr(int x){return pa[x] == x ? x : pa[x] = getr(pa[x]);}
void merge(int a, int b){
	a = getr(a), b = getr(b);
	if(a == b)return;
	pa[b] = a;
}

bool cmp(int a, int b){
	return dist[a] > dist[b];
}

void dfs(int x, int p, int d){
	par[0][x] = p;
	mx[0][x] = min(dist[x], (p == -1 ? (int)1e9 : dist[p]));
	dep[x] = d;
	for(auto i : adj2[x])if(i != p)dfs(i, x, d + 1);
}

int qry(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int diff = dep[v] - dep[u];
	int ans = min(dist[u], dist[v]);
	for(int i = 0; i < 19; i++)if(diff >> i & 1)ans = min(ans, mx[i][v]), v = par[i][v];
	if(u == v)return ans;
	for(int i = 19; i >= 0; i--){
		if(par[i][u] != par[i][v]){
			ans = min({ans, mx[i][u], mx[i][v]});
			u = par[i][u];
			v = par[i][v];
		}
	}
	return min({ans, mx[0][u], mx[0][v]});
}

void solve(){
	cin >> n >> m;
	while(m--){
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	for(int i=1;i<=n;i++)dist[i] = 1e18;
	priority_queue <pi, vector <pi>, greater <pi> > pq;
	int k; cin >> k;
	while(k--){
		int x; cin >> x;
		pq.push({0, x});
		dist[x] = 0;
	}
	while(!pq.empty()){
		int x = pq.top().fi, y = pq.top().se;
		pq.pop();
		if(dist[y] < x)continue;
		for(auto [i, j] : adj[y])if(dist[i] > x + j)dist[i] = x + j, pq.push({dist[i], i});
	}
	for(int i=1;i<=n;i++)P[i] = pa[i] = i;
	sort(P+1, P+n+1, cmp);
	for(int i=1;i<=n;i++){
		vis[P[i]] =1;
		for(auto [j, k] : adj[P[i]]){
			if(vis[j]){
				if(getr(j) != getr(P[i]))merge(j, P[i]), adj2[P[i]].push_back(j), adj2[j].push_back(P[i]);
			}
		}
	}
	dfs(1, -1, 1);
	for(int i = 1; i <= 19; i++)for(int j = 1; j <= n; j++){
		par[i][j] = par[i-1][par[i-1][j]];
		mx[i][j] = min(mx[i-1][j], mx[i-1][par[i-1][j]]);
	}
	int q; cin >> q;
	while(q--){
		int a, b; cin >> a >> b;
		cout << qry(a, b) << '\n';
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

plan.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39260 KB Output is correct
2 Correct 6 ms 39516 KB Output is correct
3 Correct 6 ms 39512 KB Output is correct
4 Correct 5 ms 39260 KB Output is correct
5 Correct 6 ms 39516 KB Output is correct
6 Correct 5 ms 39352 KB Output is correct
7 Correct 5 ms 39256 KB Output is correct
8 Correct 5 ms 39256 KB Output is correct
9 Correct 6 ms 39516 KB Output is correct
10 Correct 6 ms 39568 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 5 ms 39408 KB Output is correct
13 Correct 5 ms 39512 KB Output is correct
14 Correct 5 ms 39568 KB Output is correct
15 Correct 6 ms 39516 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39260 KB Output is correct
2 Correct 6 ms 39516 KB Output is correct
3 Correct 6 ms 39512 KB Output is correct
4 Correct 5 ms 39260 KB Output is correct
5 Correct 6 ms 39516 KB Output is correct
6 Correct 5 ms 39352 KB Output is correct
7 Correct 5 ms 39256 KB Output is correct
8 Correct 5 ms 39256 KB Output is correct
9 Correct 6 ms 39516 KB Output is correct
10 Correct 6 ms 39568 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 5 ms 39408 KB Output is correct
13 Correct 5 ms 39512 KB Output is correct
14 Correct 5 ms 39568 KB Output is correct
15 Correct 6 ms 39516 KB Output is correct
16 Correct 141 ms 51596 KB Output is correct
17 Correct 335 ms 78912 KB Output is correct
18 Correct 26 ms 42968 KB Output is correct
19 Correct 103 ms 53772 KB Output is correct
20 Correct 331 ms 79044 KB Output is correct
21 Correct 189 ms 59584 KB Output is correct
22 Correct 96 ms 56524 KB Output is correct
23 Correct 369 ms 78828 KB Output is correct
24 Correct 339 ms 79280 KB Output is correct
25 Correct 336 ms 78816 KB Output is correct
26 Correct 92 ms 53476 KB Output is correct
27 Correct 94 ms 53568 KB Output is correct
28 Correct 90 ms 53572 KB Output is correct
29 Correct 104 ms 53768 KB Output is correct
30 Correct 92 ms 53780 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 54216 KB Output is correct
2 Correct 292 ms 77208 KB Output is correct
3 Correct 307 ms 77312 KB Output is correct
4 Correct 67 ms 52692 KB Output is correct
5 Correct 275 ms 77132 KB Output is correct
6 Correct 276 ms 77248 KB Output is correct
7 Correct 285 ms 77248 KB Output is correct
8 Correct 301 ms 77128 KB Output is correct
9 Correct 320 ms 77384 KB Output is correct
10 Correct 286 ms 77248 KB Output is correct
11 Correct 314 ms 77252 KB Output is correct
12 Correct 294 ms 77300 KB Output is correct
13 Correct 270 ms 77244 KB Output is correct
14 Correct 283 ms 77252 KB Output is correct
15 Correct 332 ms 79424 KB Output is correct
16 Correct 294 ms 77252 KB Output is correct
17 Correct 282 ms 77208 KB Output is correct
18 Correct 286 ms 77584 KB Output is correct
19 Correct 66 ms 54024 KB Output is correct
20 Correct 279 ms 77252 KB Output is correct
21 Correct 274 ms 77088 KB Output is correct
22 Correct 69 ms 51956 KB Output is correct
23 Correct 83 ms 51100 KB Output is correct
24 Correct 68 ms 52032 KB Output is correct
25 Correct 74 ms 51972 KB Output is correct
26 Correct 80 ms 51380 KB Output is correct
27 Correct 71 ms 53844 KB Output is correct
28 Correct 81 ms 52076 KB Output is correct
29 Correct 66 ms 53396 KB Output is correct
30 Correct 69 ms 52032 KB Output is correct
31 Correct 70 ms 53584 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39260 KB Output is correct
2 Correct 6 ms 39516 KB Output is correct
3 Correct 6 ms 39512 KB Output is correct
4 Correct 5 ms 39260 KB Output is correct
5 Correct 6 ms 39516 KB Output is correct
6 Correct 5 ms 39352 KB Output is correct
7 Correct 5 ms 39256 KB Output is correct
8 Correct 5 ms 39256 KB Output is correct
9 Correct 6 ms 39516 KB Output is correct
10 Correct 6 ms 39568 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 5 ms 39408 KB Output is correct
13 Correct 5 ms 39512 KB Output is correct
14 Correct 5 ms 39568 KB Output is correct
15 Correct 6 ms 39516 KB Output is correct
16 Correct 141 ms 51596 KB Output is correct
17 Correct 335 ms 78912 KB Output is correct
18 Correct 26 ms 42968 KB Output is correct
19 Correct 103 ms 53772 KB Output is correct
20 Correct 331 ms 79044 KB Output is correct
21 Correct 189 ms 59584 KB Output is correct
22 Correct 96 ms 56524 KB Output is correct
23 Correct 369 ms 78828 KB Output is correct
24 Correct 339 ms 79280 KB Output is correct
25 Correct 336 ms 78816 KB Output is correct
26 Correct 92 ms 53476 KB Output is correct
27 Correct 94 ms 53568 KB Output is correct
28 Correct 90 ms 53572 KB Output is correct
29 Correct 104 ms 53768 KB Output is correct
30 Correct 92 ms 53780 KB Output is correct
31 Correct 5 ms 39256 KB Output is correct
32 Correct 6 ms 39260 KB Output is correct
33 Correct 5 ms 39260 KB Output is correct
34 Correct 5 ms 39256 KB Output is correct
35 Correct 5 ms 39260 KB Output is correct
36 Correct 5 ms 39260 KB Output is correct
37 Correct 5 ms 39260 KB Output is correct
38 Correct 5 ms 39260 KB Output is correct
39 Correct 5 ms 39260 KB Output is correct
40 Correct 5 ms 39260 KB Output is correct
41 Correct 154 ms 54216 KB Output is correct
42 Correct 292 ms 77208 KB Output is correct
43 Correct 307 ms 77312 KB Output is correct
44 Correct 67 ms 52692 KB Output is correct
45 Correct 275 ms 77132 KB Output is correct
46 Correct 276 ms 77248 KB Output is correct
47 Correct 285 ms 77248 KB Output is correct
48 Correct 301 ms 77128 KB Output is correct
49 Correct 320 ms 77384 KB Output is correct
50 Correct 286 ms 77248 KB Output is correct
51 Correct 314 ms 77252 KB Output is correct
52 Correct 294 ms 77300 KB Output is correct
53 Correct 270 ms 77244 KB Output is correct
54 Correct 283 ms 77252 KB Output is correct
55 Correct 332 ms 79424 KB Output is correct
56 Correct 294 ms 77252 KB Output is correct
57 Correct 282 ms 77208 KB Output is correct
58 Correct 286 ms 77584 KB Output is correct
59 Correct 66 ms 54024 KB Output is correct
60 Correct 279 ms 77252 KB Output is correct
61 Correct 274 ms 77088 KB Output is correct
62 Correct 69 ms 51956 KB Output is correct
63 Correct 83 ms 51100 KB Output is correct
64 Correct 68 ms 52032 KB Output is correct
65 Correct 74 ms 51972 KB Output is correct
66 Correct 80 ms 51380 KB Output is correct
67 Correct 71 ms 53844 KB Output is correct
68 Correct 81 ms 52076 KB Output is correct
69 Correct 66 ms 53396 KB Output is correct
70 Correct 69 ms 52032 KB Output is correct
71 Correct 70 ms 53584 KB Output is correct
72 Correct 225 ms 59292 KB Output is correct
73 Correct 333 ms 78888 KB Output is correct
74 Correct 393 ms 78804 KB Output is correct
75 Correct 346 ms 79096 KB Output is correct
76 Correct 326 ms 78784 KB Output is correct
77 Correct 332 ms 78884 KB Output is correct
78 Correct 342 ms 78788 KB Output is correct
79 Correct 329 ms 78792 KB Output is correct
80 Correct 341 ms 78800 KB Output is correct
81 Correct 338 ms 78928 KB Output is correct
82 Correct 369 ms 78868 KB Output is correct
83 Correct 355 ms 78808 KB Output is correct
84 Correct 347 ms 78856 KB Output is correct
85 Correct 383 ms 80572 KB Output is correct
86 Correct 374 ms 78612 KB Output is correct
87 Correct 386 ms 79040 KB Output is correct
88 Correct 364 ms 78936 KB Output is correct
89 Correct 201 ms 55492 KB Output is correct
90 Correct 349 ms 78788 KB Output is correct
91 Correct 376 ms 78804 KB Output is correct
92 Correct 115 ms 53728 KB Output is correct
93 Correct 147 ms 53072 KB Output is correct
94 Correct 116 ms 53820 KB Output is correct
95 Correct 115 ms 53568 KB Output is correct
96 Correct 158 ms 52752 KB Output is correct
97 Correct 164 ms 54608 KB Output is correct
98 Correct 108 ms 53568 KB Output is correct
99 Correct 183 ms 55820 KB Output is correct
100 Correct 124 ms 53712 KB Output is correct