oj.uz

답안 #900746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
900746 2024-01-09T01:34:04 Z aqxa Evacuation plan (IZhO18_plan) C++17
100 / 100
 378 ms 80824 KB 
// solved the problem: 
// find max spanning tree (weight of edge is min(u, v)), then answer queries 

#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:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39460 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 6 ms 39404 KB Output is correct
7 Correct 5 ms 39260 KB Output is correct
8 Correct 5 ms 39260 KB Output is correct
9 Correct 6 ms 39408 KB Output is correct
10 Correct 5 ms 39512 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 6 ms 39696 KB Output is correct
13 Correct 6 ms 39516 KB Output is correct
14 Correct 5 ms 39468 KB Output is correct
15 Correct 5 ms 39516 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39460 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 6 ms 39404 KB Output is correct
7 Correct 5 ms 39260 KB Output is correct
8 Correct 5 ms 39260 KB Output is correct
9 Correct 6 ms 39408 KB Output is correct
10 Correct 5 ms 39512 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 6 ms 39696 KB Output is correct
13 Correct 6 ms 39516 KB Output is correct
14 Correct 5 ms 39468 KB Output is correct
15 Correct 5 ms 39516 KB Output is correct
16 Correct 106 ms 51444 KB Output is correct
17 Correct 330 ms 78856 KB Output is correct
18 Correct 31 ms 43224 KB Output is correct
19 Correct 92 ms 53608 KB Output is correct
20 Correct 326 ms 79016 KB Output is correct
21 Correct 187 ms 59552 KB Output is correct
22 Correct 89 ms 56400 KB Output is correct
23 Correct 326 ms 78796 KB Output is correct
24 Correct 342 ms 78912 KB Output is correct
25 Correct 334 ms 79048 KB Output is correct
26 Correct 88 ms 53564 KB Output is correct
27 Correct 91 ms 53564 KB Output is correct
28 Correct 91 ms 53584 KB Output is correct
29 Correct 89 ms 53568 KB Output is correct
30 Correct 90 ms 53636 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 39256 KB Output is correct
2 Correct 5 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 39256 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

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 57656 KB Output is correct
2 Correct 265 ms 77088 KB Output is correct
3 Correct 295 ms 77504 KB Output is correct
4 Correct 64 ms 52564 KB Output is correct
5 Correct 273 ms 77144 KB Output is correct
6 Correct 277 ms 77284 KB Output is correct
7 Correct 281 ms 77208 KB Output is correct
8 Correct 279 ms 77252 KB Output is correct
9 Correct 271 ms 77252 KB Output is correct
10 Correct 276 ms 77252 KB Output is correct
11 Correct 262 ms 77256 KB Output is correct
12 Correct 285 ms 77252 KB Output is correct
13 Correct 279 ms 77284 KB Output is correct
14 Correct 270 ms 77336 KB Output is correct
15 Correct 278 ms 78264 KB Output is correct
16 Correct 268 ms 77256 KB Output is correct
17 Correct 263 ms 77208 KB Output is correct
18 Correct 281 ms 77264 KB Output is correct
19 Correct 64 ms 54100 KB Output is correct
20 Correct 286 ms 77248 KB Output is correct
21 Correct 275 ms 77600 KB Output is correct
22 Correct 68 ms 52124 KB Output is correct
23 Correct 73 ms 50992 KB Output is correct
24 Correct 66 ms 52100 KB Output is correct
25 Correct 69 ms 52032 KB Output is correct
26 Correct 76 ms 51564 KB Output is correct
27 Correct 68 ms 54076 KB Output is correct
28 Correct 66 ms 51940 KB Output is correct
29 Correct 71 ms 53328 KB Output is correct
30 Correct 69 ms 52064 KB Output is correct
31 Correct 65 ms 53408 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39460 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 6 ms 39404 KB Output is correct
7 Correct 5 ms 39260 KB Output is correct
8 Correct 5 ms 39260 KB Output is correct
9 Correct 6 ms 39408 KB Output is correct
10 Correct 5 ms 39512 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 6 ms 39696 KB Output is correct
13 Correct 6 ms 39516 KB Output is correct
14 Correct 5 ms 39468 KB Output is correct
15 Correct 5 ms 39516 KB Output is correct
16 Correct 106 ms 51444 KB Output is correct
17 Correct 330 ms 78856 KB Output is correct
18 Correct 31 ms 43224 KB Output is correct
19 Correct 92 ms 53608 KB Output is correct
20 Correct 326 ms 79016 KB Output is correct
21 Correct 187 ms 59552 KB Output is correct
22 Correct 89 ms 56400 KB Output is correct
23 Correct 326 ms 78796 KB Output is correct
24 Correct 342 ms 78912 KB Output is correct
25 Correct 334 ms 79048 KB Output is correct
26 Correct 88 ms 53564 KB Output is correct
27 Correct 91 ms 53564 KB Output is correct
28 Correct 91 ms 53584 KB Output is correct
29 Correct 89 ms 53568 KB Output is correct
30 Correct 90 ms 53636 KB Output is correct
31 Correct 5 ms 39256 KB Output is correct
32 Correct 5 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 39256 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 153 ms 57656 KB Output is correct
42 Correct 265 ms 77088 KB Output is correct
43 Correct 295 ms 77504 KB Output is correct
44 Correct 64 ms 52564 KB Output is correct
45 Correct 273 ms 77144 KB Output is correct
46 Correct 277 ms 77284 KB Output is correct
47 Correct 281 ms 77208 KB Output is correct
48 Correct 279 ms 77252 KB Output is correct
49 Correct 271 ms 77252 KB Output is correct
50 Correct 276 ms 77252 KB Output is correct
51 Correct 262 ms 77256 KB Output is correct
52 Correct 285 ms 77252 KB Output is correct
53 Correct 279 ms 77284 KB Output is correct
54 Correct 270 ms 77336 KB Output is correct
55 Correct 278 ms 78264 KB Output is correct
56 Correct 268 ms 77256 KB Output is correct
57 Correct 263 ms 77208 KB Output is correct
58 Correct 281 ms 77264 KB Output is correct
59 Correct 64 ms 54100 KB Output is correct
60 Correct 286 ms 77248 KB Output is correct
61 Correct 275 ms 77600 KB Output is correct
62 Correct 68 ms 52124 KB Output is correct
63 Correct 73 ms 50992 KB Output is correct
64 Correct 66 ms 52100 KB Output is correct
65 Correct 69 ms 52032 KB Output is correct
66 Correct 76 ms 51564 KB Output is correct
67 Correct 68 ms 54076 KB Output is correct
68 Correct 66 ms 51940 KB Output is correct
69 Correct 71 ms 53328 KB Output is correct
70 Correct 69 ms 52064 KB Output is correct
71 Correct 65 ms 53408 KB Output is correct
72 Correct 203 ms 59332 KB Output is correct
73 Correct 351 ms 78932 KB Output is correct
74 Correct 360 ms 78864 KB Output is correct
75 Correct 340 ms 79044 KB Output is correct
76 Correct 357 ms 78788 KB Output is correct
77 Correct 376 ms 79248 KB Output is correct
78 Correct 378 ms 78956 KB Output is correct
79 Correct 368 ms 78796 KB Output is correct
80 Correct 362 ms 78812 KB Output is correct
81 Correct 368 ms 78792 KB Output is correct
82 Correct 344 ms 78880 KB Output is correct
83 Correct 351 ms 78836 KB Output is correct
84 Correct 335 ms 78788 KB Output is correct
85 Correct 332 ms 80824 KB Output is correct
86 Correct 338 ms 78792 KB Output is correct
87 Correct 358 ms 78996 KB Output is correct
88 Correct 343 ms 78860 KB Output is correct
89 Correct 171 ms 55636 KB Output is correct
90 Correct 329 ms 78864 KB Output is correct
91 Correct 332 ms 78712 KB Output is correct
92 Correct 111 ms 53560 KB Output is correct
93 Correct 139 ms 53096 KB Output is correct
94 Correct 110 ms 53572 KB Output is correct
95 Correct 107 ms 53748 KB Output is correct
96 Correct 153 ms 52692 KB Output is correct
97 Correct 161 ms 54560 KB Output is correct
98 Correct 120 ms 53592 KB Output is correct
99 Correct 151 ms 55636 KB Output is correct
100 Correct 113 ms 53660 KB Output is correct