답안 #972000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972000	2024-04-29T16:56:14 Z	vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	477 ms	75984 KB

plan

//https://oj.uz/problem/view/IZhO18_plan
//binary lifting on mst
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using pli = pair<ll,int>;
const int N = 1e5 + 5, M = 5e5 + 5;
const ll inf = 1e18; // beaware maybe not enough
vector<pli> adj[N];
ll D[N], mn[N][20];
bool vis[N];
tuple<int,int,int> E[M];
tuple<ll,int,int> edges[M];
int p[N], up[N][20], dep[N], LOG, sz[N];
int fp(int x){if(x == p[x]) return x; return p[x] = fp(p[x]);}
void dfs(int u, int p, ll wp){
	up[u][0] = p; mn[u][0] = min(mn[u][0], wp);
	if(u != p) dep[u] = dep[p] + 1;
	for(int j = 1; j<LOG; ++j){
		up[u][j] = up[up[u][j-1]][j-1];
		mn[u][j] = min(mn[u][j-1], mn[up[u][j-1]][j-1]);
	}
	for(pli it: adj[u]){
		ll w = it.first; int v = it.second;
		if(v != p) dfs(v, u, w);
	}
}
pair<ll,int> get_lca(int u, int v){
	ll w = inf;
	if(u == v) return make_pair(w, u);
	if(dep[u] < dep[v]) swap(u, v);
	for(int j = LOG-1; j>=0; --j) if((dep[u]-dep[v])>>j&1) w = min(w, mn[u][j]), u = up[u][j];
	if(u == v) return make_pair(w, u);
	for(int j = LOG-1; j>=0; --j) if(up[u][j] != up[v][j]){w = min({w, mn[u][j], mn[v][j]}); u = up[u][j]; v = up[v][j];}
	return make_pair(min({w, mn[u][0], mn[v][0]}), up[u][0]);
}
signed main(){
	int n, m; scanf("%d %d", &n, &m); LOG = 32 - __builtin_clz(n);
	for(int i = 0, u, v, w; i<m; ++i){
		scanf("%d %d %d", &u, &v, &w); --u; --v;
		E[i] = make_tuple(u, v, w);
		adj[u].emplace_back(w, v); adj[v].emplace_back(w, u);
	}
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	fill(D, D+n, inf); fill(vis, vis+n, false);
	int k; scanf("%d", &k);
	for(int i = 0, u; i<k; ++i) scanf("%d", &u), pq.emplace(D[u-1] = 0, u-1);
	while(!pq.empty()){
		int u = pq.top().second; pq.pop();
		if(vis[u]) continue; vis[u] = true;
		for(pli it: adj[u]){
			ll w = it.first; int v = it.second;
			if(D[u] < inf && D[u] + w < D[v]) pq.emplace(D[v] = D[u] + w, v);
		}
	}
	for(int i = 0; i<m; ++i){
		int u, v, _; tie(u, v, _) = E[i];
		edges[i] = make_tuple(min(D[u], D[v]), u, v);
	}
	for(int i = 0; i<n; ++i){
		adj[i].clear(); p[i] = i; sz[i] = 1; fill(mn[i], mn[i]+LOG, inf);
	}
	sort(edges, edges+m, greater<tuple<ll,int,int>>());
	for(int i = 0; i<m; ++i){
		ll w; int u, v; tie(w, u, v) = edges[i];
		if(fp(u) != fp(v)){
			int pu = fp(u), pv = fp(v);
			if(sz[pu] < sz[pv]) swap(pu, pv);
			sz[pu] += sz[pv]; p[pv] = pu;
			adj[u].emplace_back(w, v); adj[v].emplace_back(w, u);
		}
	}
	dfs(0, 0, inf);
	int q; scanf("%d", &q);
	while(q--){
		int u, v; scanf("%d %d", &u, &v); --u; --v;
		pair<ll,int> tmp = get_lca(u, v);
		ll w = tmp.first; int lca = tmp.second;
		printf("%lld\n", w);
	}
}	

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:50:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   50 |   if(vis[u]) continue; vis[u] = true;
      |   ^~
plan.cpp:50:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   50 |   if(vis[u]) continue; vis[u] = true;
      |                        ^~~
plan.cpp:78:25: warning: unused variable 'lca' [-Wunused-variable]
   78 |   ll w = tmp.first; int lca = tmp.second;
      |                         ^~~
plan.cpp:38:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  int n, m; scanf("%d %d", &n, &m); LOG = 32 - __builtin_clz(n);
      |            ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d %d %d", &u, &v, &w); --u; --v;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  int k; scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
plan.cpp:47:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  for(int i = 0, u; i<k; ++i) scanf("%d", &u), pq.emplace(D[u-1] = 0, u-1);
      |                              ~~~~~^~~~~~~~~~
plan.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
plan.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   int u, v; scanf("%d %d", &u, &v); --u; --v;
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	14944 KB	Output is correct
2	Correct	3 ms	15192 KB	Output is correct
3	Correct	5 ms	15164 KB	Output is correct
4	Correct	2 ms	14936 KB	Output is correct
5	Correct	3 ms	15196 KB	Output is correct
6	Correct	3 ms	15196 KB	Output is correct
7	Correct	3 ms	14936 KB	Output is correct
8	Correct	2 ms	15196 KB	Output is correct
9	Correct	4 ms	15196 KB	Output is correct
10	Correct	3 ms	15192 KB	Output is correct
11	Correct	3 ms	15172 KB	Output is correct
12	Correct	3 ms	15196 KB	Output is correct
13	Correct	3 ms	15196 KB	Output is correct
14	Correct	3 ms	15196 KB	Output is correct
15	Correct	3 ms	15196 KB	Output is correct

Subtask #2

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	14944 KB	Output is correct
2	Correct	3 ms	15192 KB	Output is correct
3	Correct	5 ms	15164 KB	Output is correct
4	Correct	2 ms	14936 KB	Output is correct
5	Correct	3 ms	15196 KB	Output is correct
6	Correct	3 ms	15196 KB	Output is correct
7	Correct	3 ms	14936 KB	Output is correct
8	Correct	2 ms	15196 KB	Output is correct
9	Correct	4 ms	15196 KB	Output is correct
10	Correct	3 ms	15192 KB	Output is correct
11	Correct	3 ms	15172 KB	Output is correct
12	Correct	3 ms	15196 KB	Output is correct
13	Correct	3 ms	15196 KB	Output is correct
14	Correct	3 ms	15196 KB	Output is correct
15	Correct	3 ms	15196 KB	Output is correct
16	Correct	138 ms	41636 KB	Output is correct
17	Correct	430 ms	75616 KB	Output is correct
18	Correct	27 ms	18144 KB	Output is correct
19	Correct	113 ms	44352 KB	Output is correct
20	Correct	477 ms	75740 KB	Output is correct
21	Correct	226 ms	52928 KB	Output is correct
22	Correct	144 ms	48044 KB	Output is correct
23	Correct	411 ms	75464 KB	Output is correct
24	Correct	462 ms	75496 KB	Output is correct
25	Correct	429 ms	75460 KB	Output is correct
26	Correct	111 ms	44092 KB	Output is correct
27	Correct	130 ms	44096 KB	Output is correct
28	Correct	112 ms	44096 KB	Output is correct
29	Correct	117 ms	44180 KB	Output is correct
30	Correct	132 ms	44328 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	14940 KB	Output is correct
2	Correct	3 ms	14940 KB	Output is correct
3	Correct	2 ms	14940 KB	Output is correct
4	Correct	2 ms	15196 KB	Output is correct
5	Correct	2 ms	15152 KB	Output is correct
6	Correct	3 ms	15092 KB	Output is correct
7	Correct	2 ms	15176 KB	Output is correct
8	Correct	3 ms	14940 KB	Output is correct
9	Correct	3 ms	14940 KB	Output is correct
10	Correct	2 ms	14940 KB	Output is correct

Subtask #4

19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	188 ms	51504 KB	Output is correct
2	Correct	382 ms	74516 KB	Output is correct
3	Correct	377 ms	74512 KB	Output is correct
4	Correct	103 ms	44368 KB	Output is correct
5	Correct	370 ms	74496 KB	Output is correct
6	Correct	369 ms	74340 KB	Output is correct
7	Correct	367 ms	74488 KB	Output is correct
8	Correct	386 ms	74640 KB	Output is correct
9	Correct	364 ms	74508 KB	Output is correct
10	Correct	391 ms	74496 KB	Output is correct
11	Correct	365 ms	74520 KB	Output is correct
12	Correct	397 ms	74524 KB	Output is correct
13	Correct	393 ms	74432 KB	Output is correct
14	Correct	376 ms	74484 KB	Output is correct
15	Correct	360 ms	74864 KB	Output is correct
16	Correct	364 ms	74544 KB	Output is correct
17	Correct	374 ms	74528 KB	Output is correct
18	Correct	359 ms	74432 KB	Output is correct
19	Correct	88 ms	45908 KB	Output is correct
20	Correct	387 ms	74616 KB	Output is correct
21	Correct	374 ms	73996 KB	Output is correct
22	Correct	83 ms	43272 KB	Output is correct
23	Correct	92 ms	42440 KB	Output is correct
24	Correct	73 ms	43048 KB	Output is correct
25	Correct	72 ms	43072 KB	Output is correct
26	Correct	94 ms	42980 KB	Output is correct
27	Correct	88 ms	45652 KB	Output is correct
28	Correct	79 ms	43332 KB	Output is correct
29	Correct	87 ms	45060 KB	Output is correct
30	Correct	73 ms	43068 KB	Output is correct
31	Correct	92 ms	45136 KB	Output is correct

Subtask #5

46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	14944 KB	Output is correct
2	Correct	3 ms	15192 KB	Output is correct
3	Correct	5 ms	15164 KB	Output is correct
4	Correct	2 ms	14936 KB	Output is correct
5	Correct	3 ms	15196 KB	Output is correct
6	Correct	3 ms	15196 KB	Output is correct
7	Correct	3 ms	14936 KB	Output is correct
8	Correct	2 ms	15196 KB	Output is correct
9	Correct	4 ms	15196 KB	Output is correct
10	Correct	3 ms	15192 KB	Output is correct
11	Correct	3 ms	15172 KB	Output is correct
12	Correct	3 ms	15196 KB	Output is correct
13	Correct	3 ms	15196 KB	Output is correct
14	Correct	3 ms	15196 KB	Output is correct
15	Correct	3 ms	15196 KB	Output is correct
16	Correct	138 ms	41636 KB	Output is correct
17	Correct	430 ms	75616 KB	Output is correct
18	Correct	27 ms	18144 KB	Output is correct
19	Correct	113 ms	44352 KB	Output is correct
20	Correct	477 ms	75740 KB	Output is correct
21	Correct	226 ms	52928 KB	Output is correct
22	Correct	144 ms	48044 KB	Output is correct
23	Correct	411 ms	75464 KB	Output is correct
24	Correct	462 ms	75496 KB	Output is correct
25	Correct	429 ms	75460 KB	Output is correct
26	Correct	111 ms	44092 KB	Output is correct
27	Correct	130 ms	44096 KB	Output is correct
28	Correct	112 ms	44096 KB	Output is correct
29	Correct	117 ms	44180 KB	Output is correct
30	Correct	132 ms	44328 KB	Output is correct
31	Correct	3 ms	14940 KB	Output is correct
32	Correct	3 ms	14940 KB	Output is correct
33	Correct	2 ms	14940 KB	Output is correct
34	Correct	2 ms	15196 KB	Output is correct
35	Correct	2 ms	15152 KB	Output is correct
36	Correct	3 ms	15092 KB	Output is correct
37	Correct	2 ms	15176 KB	Output is correct
38	Correct	3 ms	14940 KB	Output is correct
39	Correct	3 ms	14940 KB	Output is correct
40	Correct	2 ms	14940 KB	Output is correct
41	Correct	188 ms	51504 KB	Output is correct
42	Correct	382 ms	74516 KB	Output is correct
43	Correct	377 ms	74512 KB	Output is correct
44	Correct	103 ms	44368 KB	Output is correct
45	Correct	370 ms	74496 KB	Output is correct
46	Correct	369 ms	74340 KB	Output is correct
47	Correct	367 ms	74488 KB	Output is correct
48	Correct	386 ms	74640 KB	Output is correct
49	Correct	364 ms	74508 KB	Output is correct
50	Correct	391 ms	74496 KB	Output is correct
51	Correct	365 ms	74520 KB	Output is correct
52	Correct	397 ms	74524 KB	Output is correct
53	Correct	393 ms	74432 KB	Output is correct
54	Correct	376 ms	74484 KB	Output is correct
55	Correct	360 ms	74864 KB	Output is correct
56	Correct	364 ms	74544 KB	Output is correct
57	Correct	374 ms	74528 KB	Output is correct
58	Correct	359 ms	74432 KB	Output is correct
59	Correct	88 ms	45908 KB	Output is correct
60	Correct	387 ms	74616 KB	Output is correct
61	Correct	374 ms	73996 KB	Output is correct
62	Correct	83 ms	43272 KB	Output is correct
63	Correct	92 ms	42440 KB	Output is correct
64	Correct	73 ms	43048 KB	Output is correct
65	Correct	72 ms	43072 KB	Output is correct
66	Correct	94 ms	42980 KB	Output is correct
67	Correct	88 ms	45652 KB	Output is correct
68	Correct	79 ms	43332 KB	Output is correct
69	Correct	87 ms	45060 KB	Output is correct
70	Correct	73 ms	43068 KB	Output is correct
71	Correct	92 ms	45136 KB	Output is correct
72	Correct	252 ms	52680 KB	Output is correct
73	Correct	419 ms	75784 KB	Output is correct
74	Correct	474 ms	75504 KB	Output is correct
75	Correct	433 ms	75536 KB	Output is correct
76	Correct	409 ms	75592 KB	Output is correct
77	Correct	402 ms	75648 KB	Output is correct
78	Correct	398 ms	75712 KB	Output is correct
79	Correct	423 ms	75460 KB	Output is correct
80	Correct	422 ms	75700 KB	Output is correct
81	Correct	423 ms	75928 KB	Output is correct
82	Correct	405 ms	75452 KB	Output is correct
83	Correct	458 ms	75512 KB	Output is correct
84	Correct	427 ms	75716 KB	Output is correct
85	Correct	457 ms	75960 KB	Output is correct
86	Correct	437 ms	75772 KB	Output is correct
87	Correct	411 ms	75500 KB	Output is correct
88	Correct	425 ms	75984 KB	Output is correct
89	Correct	163 ms	46840 KB	Output is correct
90	Correct	474 ms	75612 KB	Output is correct
91	Correct	407 ms	75056 KB	Output is correct
92	Correct	125 ms	44328 KB	Output is correct
93	Correct	148 ms	44084 KB	Output is correct
94	Correct	115 ms	44008 KB	Output is correct
95	Correct	118 ms	44328 KB	Output is correct
96	Correct	163 ms	43708 KB	Output is correct
97	Correct	176 ms	45684 KB	Output is correct
98	Correct	133 ms	44088 KB	Output is correct
99	Correct	188 ms	47076 KB	Output is correct
100	Correct	122 ms	44284 KB	Output is correct