oj.uz

답안 #291693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291693 2020-09-05T16:31:13 Z nvmdava 자매 도시 (APIO20_swap) C++17
100 / 100
 431 ms 31768 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1000000005;
#define ff first
#define ss second

vector<pair<int, pair<int, int> > > edge;
vector<pair<int, int> > dsu[N];
int ans[N];
int d[N];
vector<int> gr[N];

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	cerr<<"BEGIN";
	for(int i = 0; i < N; ++i)
		ans[i] = INF;
	for(int i = 0; i < N; ++i){
		dsu[i].push_back({0, i});
		gr[i].push_back(i);
	}

	for(int i = 0; i < M; ++i)
		edge.push_back({W[i], {V[i], U[i]}});
	sort(edge.begin(), edge.end());

	for(auto& wtf : edge){
		int v = wtf.ss.ff;
		int u = wtf.ss.ss;
		int w = wtf.ff;

		int vv = dsu[v].back().ss;
		int uu = dsu[u].back().ss;

		if(vv == uu){
			ans[vv] = min(ans[vv], w);
			continue;
		}

		++d[v];
		++d[u];

		if(gr[vv].size() > gr[uu].size()){
			swap(vv, uu);
			swap(v, u);
		}
		ans[uu] = min(ans[uu], max(w, ans[vv]));
		if(d[v] >= 3 || d[u] >= 3){
			ans[uu] = min(ans[uu], w);
		}
		for(auto& x : gr[vv]){
			gr[uu].push_back(x);
			dsu[x].push_back({w, uu});
		}
	}
}

int getMinimumFuelCapacity(int x, int y){
	int ix = dsu[x].size() - 1;
	int iy = dsu[y].size() - 1;
	int w = INF, mn = INF;
	while(ix >= 0 && iy >= 0 && dsu[x][ix].ss == dsu[y][iy].ss){
		w = max(dsu[x][ix].ff, dsu[y][iy].ff);
		mn = min(mn, max(w, ans[dsu[x][ix].ss]));
		--ix; --iy;
	}
	w = max(w, mn);
	return (w == INF ? -1 : w);
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 5 ms 5248 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 186 ms 21748 KB Output is correct
10 Correct 235 ms 25112 KB Output is correct
11 Correct 227 ms 24684 KB Output is correct
12 Correct 256 ms 25948 KB Output is correct
13 Correct 140 ms 18520 KB Output is correct
14 Correct 182 ms 21740 KB Output is correct
15 Correct 327 ms 27384 KB Output is correct
16 Correct 324 ms 26652 KB Output is correct
17 Correct 364 ms 27984 KB Output is correct
18 Correct 235 ms 20436 KB Output is correct
19 Correct 93 ms 11576 KB Output is correct
20 Correct 329 ms 28408 KB Output is correct
21 Correct 319 ms 27944 KB Output is correct
22 Correct 347 ms 29540 KB Output is correct
23 Correct 241 ms 21840 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 203 ms 18960 KB Output is correct
4 Correct 201 ms 19408 KB Output is correct
5 Correct 202 ms 19400 KB Output is correct
6 Correct 200 ms 19284 KB Output is correct
7 Correct 211 ms 19436 KB Output is correct
8 Correct 195 ms 18980 KB Output is correct
9 Correct 205 ms 19304 KB Output is correct
10 Correct 199 ms 18888 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 5 ms 5120 KB Output is correct
11 Correct 5 ms 5248 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct
13 Correct 5 ms 5120 KB Output is correct
14 Correct 5 ms 5120 KB Output is correct
15 Correct 5 ms 5248 KB Output is correct
16 Correct 5 ms 5248 KB Output is correct
17 Correct 4 ms 5120 KB Output is correct
18 Correct 5 ms 5120 KB Output is correct
19 Correct 4 ms 5120 KB Output is correct
20 Correct 5 ms 5248 KB Output is correct
21 Correct 5 ms 5120 KB Output is correct
22 Correct 5 ms 5120 KB Output is correct
23 Correct 4 ms 5120 KB Output is correct
24 Correct 5 ms 5248 KB Output is correct
25 Correct 5 ms 5248 KB Output is correct
26 Correct 5 ms 5248 KB Output is correct
27 Correct 4 ms 5120 KB Output is correct
28 Correct 5 ms 5248 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 186 ms 21748 KB Output is correct
11 Correct 235 ms 25112 KB Output is correct
12 Correct 227 ms 24684 KB Output is correct
13 Correct 256 ms 25948 KB Output is correct
14 Correct 140 ms 18520 KB Output is correct
15 Correct 5 ms 5120 KB Output is correct
16 Correct 5 ms 5248 KB Output is correct
17 Correct 4 ms 5120 KB Output is correct
18 Correct 5 ms 5120 KB Output is correct
19 Correct 5 ms 5120 KB Output is correct
20 Correct 5 ms 5248 KB Output is correct
21 Correct 5 ms 5248 KB Output is correct
22 Correct 4 ms 5120 KB Output is correct
23 Correct 5 ms 5120 KB Output is correct
24 Correct 21 ms 7488 KB Output is correct
25 Correct 227 ms 25828 KB Output is correct
26 Correct 226 ms 25564 KB Output is correct
27 Correct 219 ms 25200 KB Output is correct
28 Correct 214 ms 24308 KB Output is correct
29 Correct 213 ms 23916 KB Output is correct
30 Correct 184 ms 22040 KB Output is correct
31 Correct 230 ms 26220 KB Output is correct
32 Correct 235 ms 26288 KB Output is correct
33 Correct 123 ms 17772 KB Output is correct
34 Correct 214 ms 23660 KB Output is correct
35 Correct 4 ms 5120 KB Output is correct
36 Correct 5 ms 5248 KB Output is correct
37 Correct 5 ms 5120 KB Output is correct
38 Correct 5 ms 5120 KB Output is correct
39 Correct 4 ms 5120 KB Output is correct
40 Correct 5 ms 5248 KB Output is correct
41 Correct 5 ms 5248 KB Output is correct
42 Correct 5 ms 5248 KB Output is correct
43 Correct 4 ms 5120 KB Output is correct
44 Correct 5 ms 5248 KB Output is correct
45 Correct 177 ms 18688 KB Output is correct
46 Correct 230 ms 25516 KB Output is correct
47 Correct 193 ms 22124 KB Output is correct
48 Correct 162 ms 19436 KB Output is correct
49 Correct 92 ms 12012 KB Output is correct
50 Correct 80 ms 10092 KB Output is correct
51 Correct 142 ms 16236 KB Output is correct
52 Correct 274 ms 27008 KB Output is correct
53 Correct 241 ms 22656 KB Output is correct
54 Correct 303 ms 29928 KB Output is correct
55 Correct 126 ms 18028 KB Output is correct
56 Correct 228 ms 21864 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 5 ms 5248 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 186 ms 21748 KB Output is correct
10 Correct 235 ms 25112 KB Output is correct
11 Correct 227 ms 24684 KB Output is correct
12 Correct 256 ms 25948 KB Output is correct
13 Correct 140 ms 18520 KB Output is correct
14 Correct 182 ms 21740 KB Output is correct
15 Correct 327 ms 27384 KB Output is correct
16 Correct 324 ms 26652 KB Output is correct
17 Correct 364 ms 27984 KB Output is correct
18 Correct 235 ms 20436 KB Output is correct
19 Correct 203 ms 18960 KB Output is correct
20 Correct 201 ms 19408 KB Output is correct
21 Correct 202 ms 19400 KB Output is correct
22 Correct 200 ms 19284 KB Output is correct
23 Correct 211 ms 19436 KB Output is correct
24 Correct 195 ms 18980 KB Output is correct
25 Correct 205 ms 19304 KB Output is correct
26 Correct 199 ms 18888 KB Output is correct
27 Correct 5 ms 5120 KB Output is correct
28 Correct 5 ms 5248 KB Output is correct
29 Correct 4 ms 5120 KB Output is correct
30 Correct 5 ms 5120 KB Output is correct
31 Correct 5 ms 5120 KB Output is correct
32 Correct 5 ms 5248 KB Output is correct
33 Correct 5 ms 5248 KB Output is correct
34 Correct 4 ms 5120 KB Output is correct
35 Correct 5 ms 5120 KB Output is correct
36 Correct 21 ms 7488 KB Output is correct
37 Correct 227 ms 25828 KB Output is correct
38 Correct 226 ms 25564 KB Output is correct
39 Correct 219 ms 25200 KB Output is correct
40 Correct 214 ms 24308 KB Output is correct
41 Correct 213 ms 23916 KB Output is correct
42 Correct 184 ms 22040 KB Output is correct
43 Correct 230 ms 26220 KB Output is correct
44 Correct 235 ms 26288 KB Output is correct
45 Correct 123 ms 17772 KB Output is correct
46 Correct 214 ms 23660 KB Output is correct
47 Correct 29 ms 7632 KB Output is correct
48 Correct 338 ms 28624 KB Output is correct
49 Correct 335 ms 27860 KB Output is correct
50 Correct 344 ms 27856 KB Output is correct
51 Correct 326 ms 27336 KB Output is correct
52 Correct 324 ms 25628 KB Output is correct
53 Correct 231 ms 20960 KB Output is correct
54 Correct 351 ms 29000 KB Output is correct
55 Correct 331 ms 29140 KB Output is correct
56 Correct 230 ms 20944 KB Output is correct
57 Correct 310 ms 26576 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 186 ms 21748 KB Output is correct
11 Correct 235 ms 25112 KB Output is correct
12 Correct 227 ms 24684 KB Output is correct
13 Correct 256 ms 25948 KB Output is correct
14 Correct 140 ms 18520 KB Output is correct
15 Correct 182 ms 21740 KB Output is correct
16 Correct 327 ms 27384 KB Output is correct
17 Correct 324 ms 26652 KB Output is correct
18 Correct 364 ms 27984 KB Output is correct
19 Correct 235 ms 20436 KB Output is correct
20 Correct 203 ms 18960 KB Output is correct
21 Correct 201 ms 19408 KB Output is correct
22 Correct 202 ms 19400 KB Output is correct
23 Correct 200 ms 19284 KB Output is correct
24 Correct 211 ms 19436 KB Output is correct
25 Correct 195 ms 18980 KB Output is correct
26 Correct 205 ms 19304 KB Output is correct
27 Correct 199 ms 18888 KB Output is correct
28 Correct 5 ms 5120 KB Output is correct
29 Correct 5 ms 5248 KB Output is correct
30 Correct 4 ms 5120 KB Output is correct
31 Correct 5 ms 5120 KB Output is correct
32 Correct 5 ms 5120 KB Output is correct
33 Correct 5 ms 5248 KB Output is correct
34 Correct 5 ms 5248 KB Output is correct
35 Correct 4 ms 5120 KB Output is correct
36 Correct 5 ms 5120 KB Output is correct
37 Correct 21 ms 7488 KB Output is correct
38 Correct 227 ms 25828 KB Output is correct
39 Correct 226 ms 25564 KB Output is correct
40 Correct 219 ms 25200 KB Output is correct
41 Correct 214 ms 24308 KB Output is correct
42 Correct 213 ms 23916 KB Output is correct
43 Correct 184 ms 22040 KB Output is correct
44 Correct 230 ms 26220 KB Output is correct
45 Correct 235 ms 26288 KB Output is correct
46 Correct 123 ms 17772 KB Output is correct
47 Correct 214 ms 23660 KB Output is correct
48 Correct 29 ms 7632 KB Output is correct
49 Correct 338 ms 28624 KB Output is correct
50 Correct 335 ms 27860 KB Output is correct
51 Correct 344 ms 27856 KB Output is correct
52 Correct 326 ms 27336 KB Output is correct
53 Correct 324 ms 25628 KB Output is correct
54 Correct 231 ms 20960 KB Output is correct
55 Correct 351 ms 29000 KB Output is correct
56 Correct 331 ms 29140 KB Output is correct
57 Correct 230 ms 20944 KB Output is correct
58 Correct 310 ms 26576 KB Output is correct
59 Correct 93 ms 11576 KB Output is correct
60 Correct 329 ms 28408 KB Output is correct
61 Correct 319 ms 27944 KB Output is correct
62 Correct 347 ms 29540 KB Output is correct
63 Correct 241 ms 21840 KB Output is correct
64 Correct 4 ms 5120 KB Output is correct
65 Correct 5 ms 5248 KB Output is correct
66 Correct 5 ms 5120 KB Output is correct
67 Correct 5 ms 5120 KB Output is correct
68 Correct 4 ms 5120 KB Output is correct
69 Correct 5 ms 5248 KB Output is correct
70 Correct 5 ms 5248 KB Output is correct
71 Correct 5 ms 5248 KB Output is correct
72 Correct 4 ms 5120 KB Output is correct
73 Correct 5 ms 5248 KB Output is correct
74 Correct 177 ms 18688 KB Output is correct
75 Correct 230 ms 25516 KB Output is correct
76 Correct 193 ms 22124 KB Output is correct
77 Correct 162 ms 19436 KB Output is correct
78 Correct 92 ms 12012 KB Output is correct
79 Correct 80 ms 10092 KB Output is correct
80 Correct 142 ms 16236 KB Output is correct
81 Correct 274 ms 27008 KB Output is correct
82 Correct 241 ms 22656 KB Output is correct
83 Correct 303 ms 29928 KB Output is correct
84 Correct 126 ms 18028 KB Output is correct
85 Correct 228 ms 21864 KB Output is correct
86 Correct 72 ms 10660 KB Output is correct
87 Correct 339 ms 27500 KB Output is correct
88 Correct 336 ms 27604 KB Output is correct
89 Correct 259 ms 21132 KB Output is correct
90 Correct 190 ms 13932 KB Output is correct
91 Correct 189 ms 14060 KB Output is correct
92 Correct 240 ms 19016 KB Output is correct
93 Correct 386 ms 28692 KB Output is correct
94 Correct 360 ms 25416 KB Output is correct
95 Correct 431 ms 31768 KB Output is correct
96 Correct 241 ms 20968 KB Output is correct
97 Correct 303 ms 23456 KB Output is correct