oj.uz

Submission #328046

# Submission time Handle Problem Language Result Execution time Memory
328046 2020-11-15T09:30:49 Z admin Swapping Cities (APIO20_swap) C++17
100 / 100
 643 ms 59748 KB 
// https://raw.githubusercontent.com/koosaga/olympiad/master/APIO/apio20_swap.cpp
 
#include "swap.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;
const int mod = 1e9 + 7;
 
struct disj{
	struct node{
		int pa, max_deg, cycle, updated;
		bool operator<(const node &n)const{
			return updated < n.updated;
		}
	};
	// persistent
	vector<node> nodes[MAXN];
 
	// only used in creation
	vector<int> memb[MAXN];
	int deg[MAXN];
	void init(int n){
		for(int i=0; i<n; i++){
			memb[i].push_back(i);
			nodes[i].push_back({i, 0, 0, -1});
		}
	}
	int find(int x){
		return nodes[x].back().pa;
	}
	void add_edge(int x, int y, int i){
		deg[x]++; deg[y]++;
		int new_deg = max(deg[x], deg[y]);
		x = find(x); y = find(y);
		if(x != y){
			if(sz(memb[x]) < sz(memb[y])) swap(x, y);
			for(auto &v : memb[y]){
				node prv = nodes[v].back();
				prv.pa = x;
				prv.updated = i;
				nodes[v].push_back(prv);
				memb[x].push_back(v);
			}
			node prv = nodes[x].back();
			prv.max_deg = max(prv.max_deg, nodes[y].back().max_deg);
			prv.cycle |= nodes[y].back().cycle;
			prv.updated = i;
			nodes[x].push_back(prv);
			memb[y].clear();
		}
		node prv = nodes[x].back();
		if(x == y) prv.cycle = 1;
		prv.max_deg = max(prv.max_deg, new_deg);
		prv.updated = i;
		nodes[x].push_back(prv);
	}
	node get_node(int x, int t){
		return *--upper_bound(all(nodes[x]), (node){-1, -1, 0, t});
	}
}disj;
 
bool isGood(int u, int v, int m){
	auto gnx = disj.get_node(u, m);
	auto gny = disj.get_node(v, m);
	if(gnx.pa != gny.pa) return 0;
	auto val = disj.get_node(gnx.pa, m);
	return val.max_deg >= 3 || val.cycle;
}
 
int n, m;
 
struct edg{
	int s, e, x;
}a[MAXN];
 
void init(int N, int M,
		std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N; m = M;
	disj.init(n);
	for(int i=0; i<M; i++) a[i] = {U[i], V[i], W[i]};
	sort(a, a + M, [&](const edg &a, const edg &b){
		return a.x < b.x;
	});
	for(int i=0; i<M; i++) disj.add_edge(a[i].s, a[i].e, i);
}
 
int getMinimumFuelCapacity(int X, int Y) {
	int s = 0, e = m;
	while(s != e){
		int m = (s + e) / 2;
		if(isGood(X, Y, m)) e = m;
		else s = m + 1;
	}
	if(s == m) return -1;
	return a[s].x;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 8 ms 9964 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 10 ms 9964 KB Output is correct
9 Correct 194 ms 39264 KB Output is correct
10 Correct 250 ms 45288 KB Output is correct
11 Correct 230 ms 44660 KB Output is correct
12 Correct 255 ms 46948 KB Output is correct
13 Correct 127 ms 32972 KB Output is correct
14 Correct 206 ms 39268 KB Output is correct
15 Correct 480 ms 50416 KB Output is correct
16 Correct 458 ms 49092 KB Output is correct
17 Correct 492 ms 51660 KB Output is correct
18 Correct 317 ms 37044 KB Output is correct
19 Correct 162 ms 20204 KB Output is correct
20 Correct 471 ms 51296 KB Output is correct
21 Correct 464 ms 50356 KB Output is correct
22 Correct 494 ms 52808 KB Output is correct
23 Correct 326 ms 38452 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 424 ms 34052 KB Output is correct
4 Correct 423 ms 34744 KB Output is correct
5 Correct 447 ms 34536 KB Output is correct
6 Correct 417 ms 34716 KB Output is correct
7 Correct 460 ms 34896 KB Output is correct
8 Correct 416 ms 33920 KB Output is correct
9 Correct 461 ms 34644 KB Output is correct
10 Correct 421 ms 33804 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 8 ms 9964 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 10 ms 9964 KB Output is correct
9 Correct 6 ms 9708 KB Output is correct
10 Correct 7 ms 9964 KB Output is correct
11 Correct 8 ms 9964 KB Output is correct
12 Correct 8 ms 9964 KB Output is correct
13 Correct 8 ms 9964 KB Output is correct
14 Correct 8 ms 9964 KB Output is correct
15 Correct 9 ms 10092 KB Output is correct
16 Correct 8 ms 10092 KB Output is correct
17 Correct 8 ms 9964 KB Output is correct
18 Correct 8 ms 9964 KB Output is correct
19 Correct 8 ms 9964 KB Output is correct
20 Correct 8 ms 9964 KB Output is correct
21 Correct 8 ms 9964 KB Output is correct
22 Correct 8 ms 9964 KB Output is correct
23 Correct 9 ms 9964 KB Output is correct
24 Correct 8 ms 10092 KB Output is correct
25 Correct 8 ms 10092 KB Output is correct
26 Correct 8 ms 10092 KB Output is correct
27 Correct 8 ms 9964 KB Output is correct
28 Correct 9 ms 10220 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 8 ms 9964 KB Output is correct
7 Correct 9 ms 9964 KB Output is correct
8 Correct 8 ms 10092 KB Output is correct
9 Correct 10 ms 9964 KB Output is correct
10 Correct 194 ms 39264 KB Output is correct
11 Correct 250 ms 45288 KB Output is correct
12 Correct 230 ms 44660 KB Output is correct
13 Correct 255 ms 46948 KB Output is correct
14 Correct 127 ms 32972 KB Output is correct
15 Correct 7 ms 9964 KB Output is correct
16 Correct 8 ms 9964 KB Output is correct
17 Correct 8 ms 9964 KB Output is correct
18 Correct 8 ms 9964 KB Output is correct
19 Correct 8 ms 9964 KB Output is correct
20 Correct 9 ms 10092 KB Output is correct
21 Correct 8 ms 10092 KB Output is correct
22 Correct 8 ms 9964 KB Output is correct
23 Correct 8 ms 9964 KB Output is correct
24 Correct 8 ms 9964 KB Output is correct
25 Correct 8 ms 9964 KB Output is correct
26 Correct 8 ms 9964 KB Output is correct
27 Correct 8 ms 9964 KB Output is correct
28 Correct 9 ms 9964 KB Output is correct
29 Correct 8 ms 10092 KB Output is correct
30 Correct 8 ms 10092 KB Output is correct
31 Correct 8 ms 10092 KB Output is correct
32 Correct 8 ms 9964 KB Output is correct
33 Correct 9 ms 10220 KB Output is correct
34 Correct 24 ms 13932 KB Output is correct
35 Correct 255 ms 46512 KB Output is correct
36 Correct 254 ms 45796 KB Output is correct
37 Correct 252 ms 44852 KB Output is correct
38 Correct 224 ms 43060 KB Output is correct
39 Correct 274 ms 42596 KB Output is correct
40 Correct 201 ms 39012 KB Output is correct
41 Correct 252 ms 47712 KB Output is correct
42 Correct 298 ms 47456 KB Output is correct
43 Correct 131 ms 32348 KB Output is correct
44 Correct 213 ms 42340 KB Output is correct
45 Correct 190 ms 34008 KB Output is correct
46 Correct 271 ms 45668 KB Output is correct
47 Correct 210 ms 40036 KB Output is correct
48 Correct 171 ms 34904 KB Output is correct
49 Correct 77 ms 22492 KB Output is correct
50 Correct 72 ms 19680 KB Output is correct
51 Correct 155 ms 30300 KB Output is correct
52 Correct 281 ms 49284 KB Output is correct
53 Correct 255 ms 43868 KB Output is correct
54 Correct 348 ms 55092 KB Output is correct
55 Correct 124 ms 32464 KB Output is correct
56 Correct 250 ms 41696 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 8 ms 9964 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 10 ms 9964 KB Output is correct
9 Correct 194 ms 39264 KB Output is correct
10 Correct 250 ms 45288 KB Output is correct
11 Correct 230 ms 44660 KB Output is correct
12 Correct 255 ms 46948 KB Output is correct
13 Correct 127 ms 32972 KB Output is correct
14 Correct 206 ms 39268 KB Output is correct
15 Correct 480 ms 50416 KB Output is correct
16 Correct 458 ms 49092 KB Output is correct
17 Correct 492 ms 51660 KB Output is correct
18 Correct 317 ms 37044 KB Output is correct
19 Correct 424 ms 34052 KB Output is correct
20 Correct 423 ms 34744 KB Output is correct
21 Correct 447 ms 34536 KB Output is correct
22 Correct 417 ms 34716 KB Output is correct
23 Correct 460 ms 34896 KB Output is correct
24 Correct 416 ms 33920 KB Output is correct
25 Correct 461 ms 34644 KB Output is correct
26 Correct 421 ms 33804 KB Output is correct
27 Correct 7 ms 9964 KB Output is correct
28 Correct 8 ms 9964 KB Output is correct
29 Correct 8 ms 9964 KB Output is correct
30 Correct 8 ms 9964 KB Output is correct
31 Correct 8 ms 9964 KB Output is correct
32 Correct 9 ms 10092 KB Output is correct
33 Correct 8 ms 10092 KB Output is correct
34 Correct 8 ms 9964 KB Output is correct
35 Correct 8 ms 9964 KB Output is correct
36 Correct 24 ms 13932 KB Output is correct
37 Correct 255 ms 46512 KB Output is correct
38 Correct 254 ms 45796 KB Output is correct
39 Correct 252 ms 44852 KB Output is correct
40 Correct 224 ms 43060 KB Output is correct
41 Correct 274 ms 42596 KB Output is correct
42 Correct 201 ms 39012 KB Output is correct
43 Correct 252 ms 47712 KB Output is correct
44 Correct 298 ms 47456 KB Output is correct
45 Correct 131 ms 32348 KB Output is correct
46 Correct 213 ms 42340 KB Output is correct
47 Correct 39 ms 14188 KB Output is correct
48 Correct 490 ms 51400 KB Output is correct
49 Correct 505 ms 49996 KB Output is correct
50 Correct 523 ms 49740 KB Output is correct
51 Correct 478 ms 48728 KB Output is correct
52 Correct 515 ms 45844 KB Output is correct
53 Correct 380 ms 37012 KB Output is correct
54 Correct 496 ms 52064 KB Output is correct
55 Correct 525 ms 52936 KB Output is correct
56 Correct 410 ms 37632 KB Output is correct
57 Correct 488 ms 47308 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 8 ms 9964 KB Output is correct
7 Correct 9 ms 9964 KB Output is correct
8 Correct 8 ms 10092 KB Output is correct
9 Correct 10 ms 9964 KB Output is correct
10 Correct 194 ms 39264 KB Output is correct
11 Correct 250 ms 45288 KB Output is correct
12 Correct 230 ms 44660 KB Output is correct
13 Correct 255 ms 46948 KB Output is correct
14 Correct 127 ms 32972 KB Output is correct
15 Correct 206 ms 39268 KB Output is correct
16 Correct 480 ms 50416 KB Output is correct
17 Correct 458 ms 49092 KB Output is correct
18 Correct 492 ms 51660 KB Output is correct
19 Correct 317 ms 37044 KB Output is correct
20 Correct 424 ms 34052 KB Output is correct
21 Correct 423 ms 34744 KB Output is correct
22 Correct 447 ms 34536 KB Output is correct
23 Correct 417 ms 34716 KB Output is correct
24 Correct 460 ms 34896 KB Output is correct
25 Correct 416 ms 33920 KB Output is correct
26 Correct 461 ms 34644 KB Output is correct
27 Correct 421 ms 33804 KB Output is correct
28 Correct 7 ms 9964 KB Output is correct
29 Correct 8 ms 9964 KB Output is correct
30 Correct 8 ms 9964 KB Output is correct
31 Correct 8 ms 9964 KB Output is correct
32 Correct 8 ms 9964 KB Output is correct
33 Correct 9 ms 10092 KB Output is correct
34 Correct 8 ms 10092 KB Output is correct
35 Correct 8 ms 9964 KB Output is correct
36 Correct 8 ms 9964 KB Output is correct
37 Correct 24 ms 13932 KB Output is correct
38 Correct 255 ms 46512 KB Output is correct
39 Correct 254 ms 45796 KB Output is correct
40 Correct 252 ms 44852 KB Output is correct
41 Correct 224 ms 43060 KB Output is correct
42 Correct 274 ms 42596 KB Output is correct
43 Correct 201 ms 39012 KB Output is correct
44 Correct 252 ms 47712 KB Output is correct
45 Correct 298 ms 47456 KB Output is correct
46 Correct 131 ms 32348 KB Output is correct
47 Correct 213 ms 42340 KB Output is correct
48 Correct 39 ms 14188 KB Output is correct
49 Correct 490 ms 51400 KB Output is correct
50 Correct 505 ms 49996 KB Output is correct
51 Correct 523 ms 49740 KB Output is correct
52 Correct 478 ms 48728 KB Output is correct
53 Correct 515 ms 45844 KB Output is correct
54 Correct 380 ms 37012 KB Output is correct
55 Correct 496 ms 52064 KB Output is correct
56 Correct 525 ms 52936 KB Output is correct
57 Correct 410 ms 37632 KB Output is correct
58 Correct 488 ms 47308 KB Output is correct
59 Correct 162 ms 20204 KB Output is correct
60 Correct 471 ms 51296 KB Output is correct
61 Correct 464 ms 50356 KB Output is correct
62 Correct 494 ms 52808 KB Output is correct
63 Correct 326 ms 38452 KB Output is correct
64 Correct 8 ms 9964 KB Output is correct
65 Correct 8 ms 9964 KB Output is correct
66 Correct 8 ms 9964 KB Output is correct
67 Correct 8 ms 9964 KB Output is correct
68 Correct 9 ms 9964 KB Output is correct
69 Correct 8 ms 10092 KB Output is correct
70 Correct 8 ms 10092 KB Output is correct
71 Correct 8 ms 10092 KB Output is correct
72 Correct 8 ms 9964 KB Output is correct
73 Correct 9 ms 10220 KB Output is correct
74 Correct 190 ms 34008 KB Output is correct
75 Correct 271 ms 45668 KB Output is correct
76 Correct 210 ms 40036 KB Output is correct
77 Correct 171 ms 34904 KB Output is correct
78 Correct 77 ms 22492 KB Output is correct
79 Correct 72 ms 19680 KB Output is correct
80 Correct 155 ms 30300 KB Output is correct
81 Correct 281 ms 49284 KB Output is correct
82 Correct 255 ms 43868 KB Output is correct
83 Correct 348 ms 55092 KB Output is correct
84 Correct 124 ms 32464 KB Output is correct
85 Correct 250 ms 41696 KB Output is correct
86 Correct 154 ms 20132 KB Output is correct
87 Correct 484 ms 49124 KB Output is correct
88 Correct 490 ms 49484 KB Output is correct
89 Correct 518 ms 38488 KB Output is correct
90 Correct 346 ms 26460 KB Output is correct
91 Correct 378 ms 27612 KB Output is correct
92 Correct 506 ms 34872 KB Output is correct
93 Correct 582 ms 52792 KB Output is correct
94 Correct 643 ms 48480 KB Output is correct
95 Correct 606 ms 59748 KB Output is correct
96 Correct 406 ms 37536 KB Output is correct
97 Correct 579 ms 42644 KB Output is correct