oj.uz

Submission #1012044

# Submission time Handle Problem Language Result Execution time Memory
1012044 2024-07-01T15:03:35 Z AmirAli_H1 Parachute rings (IOI12_rings) C++17
100 / 100
 866 ms 138920 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 4;

int n;
vector<int> adj[maxn];
vector<pii> E; pii delta;
int p[4][maxn], sz[4][maxn];
int numx[4], valx[4], R, Rx; pii val[4][maxn];

int get(int ind, int u) {
	return p[ind][u] == u ? u : p[ind][u] = get(ind, p[ind][u]);
}

void merge(int ind, int ux, int vx) {
	int u = get(ind, ux), v = get(ind, vx);
	if (sz[ind][u] > sz[ind][v]) {
		swap(ux, vx); swap(u, v);
	}
	
	if (u == v) {
		numx[ind]++; Rx = sz[ind][v];
		return ;
	}
	int u1 = val[ind][u].F, u2 = val[ind][u].S;
	int v1 = val[ind][v].F, v2 = val[ind][v].S;
	for (int T1 = 0; T1 < 2; T1++) {
		for (int T2 = 0; T2 < 2; T2++) {
			if (u2 == ux && v2 == vx) {
				p[ind][u] = v; sz[ind][v] += sz[ind][u];
				val[ind][v] = Mp(u1, v1);
				return ;
			}
			swap(v1, v2);
		}
		swap(u1, u2);
	}
	numx[ind]++; Rx = sz[ind][v];
	return ;
}

void build(int ind, int x) {
	numx[ind] = 0; valx[ind] = x;
	for (int i = 0; i < n; i++) {
		p[ind][i] = i; sz[ind][i] = 1;
		val[ind][i] = Mp(i, i);
	}
	for (auto f : E) {
		int u = f.F, v = f.S;
		if (u == valx[ind] || v == valx[ind]) continue;
		merge(ind, u, v);
	}
}

void rebuild3() {
	int v = delta.S; R = 0;
	build(R, v); R++;
	for (int u : adj[v]) {
		build(R, u); R++;
	}
}

void rebuild4() {
	int v = delta.S; R = 0;
	build(R, v); R++;
}

void Init(int N) {
	n = N; delta = Mp(0, 0);
	R = 1; build(0, -1);
}

void Link(int u, int v) {
	E.pb(Mp(u, v));
	adj[u].pb(v); adj[v].pb(u);
	for (int i = 0; i < R; i++) {
		if (u == valx[i] || v == valx[i]) continue;
		merge(i, u, v);
	}
	for (int x : {u, v}) {
		if (len(adj[x]) > delta.F) {
			delta = Mp(len(adj[x]), x);
			if (delta.F == 3) rebuild3();
			else if (delta.F == 4) rebuild4();
		}
	}
}

int CountCritical() {
	if (delta.F <= 1) return n;
	else if (delta.F == 2) {
		if (numx[0] == 0) return n;
		else if (numx[0] == 1) return Rx;
		else return 0;
	}
	else {
		int ans = 0;
		for (int i = 0; i < R; i++) {
			if (numx[i] == 0) ans++;
		}
		return ans;
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24664 KB Output is correct
2 Correct 13 ms 25436 KB Output is correct
3 Correct 14 ms 25536 KB Output is correct
4 Correct 10 ms 24812 KB Output is correct
5 Correct 10 ms 24944 KB Output is correct
6 Correct 12 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 11 ms 24924 KB Output is correct
9 Correct 11 ms 25436 KB Output is correct
10 Correct 11 ms 25436 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 60140 KB Output is correct
2 Correct 589 ms 116636 KB Output is correct
3 Correct 633 ms 133804 KB Output is correct
4 Correct 668 ms 92968 KB Output is correct
5 Correct 637 ms 92840 KB Output is correct
6 Correct 618 ms 91156 KB Output is correct
7 Correct 575 ms 132324 KB Output is correct
8 Correct 837 ms 131756 KB Output is correct
9 Correct 866 ms 138920 KB Output is correct
10 Correct 451 ms 90024 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24664 KB Output is correct
2 Correct 13 ms 25436 KB Output is correct
3 Correct 14 ms 25536 KB Output is correct
4 Correct 10 ms 24812 KB Output is correct
5 Correct 10 ms 24944 KB Output is correct
6 Correct 12 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 11 ms 24924 KB Output is correct
9 Correct 11 ms 25436 KB Output is correct
10 Correct 11 ms 25436 KB Output is correct
11 Correct 11 ms 25436 KB Output is correct
12 Correct 13 ms 25948 KB Output is correct
13 Correct 13 ms 25948 KB Output is correct
14 Correct 11 ms 25692 KB Output is correct
15 Correct 12 ms 26416 KB Output is correct
16 Correct 13 ms 25436 KB Output is correct
17 Correct 12 ms 26012 KB Output is correct
18 Correct 13 ms 26716 KB Output is correct
19 Correct 12 ms 25524 KB Output is correct
20 Correct 13 ms 25944 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24664 KB Output is correct
2 Correct 13 ms 25436 KB Output is correct
3 Correct 14 ms 25536 KB Output is correct
4 Correct 10 ms 24812 KB Output is correct
5 Correct 10 ms 24944 KB Output is correct
6 Correct 12 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 11 ms 24924 KB Output is correct
9 Correct 11 ms 25436 KB Output is correct
10 Correct 11 ms 25436 KB Output is correct
11 Correct 11 ms 25436 KB Output is correct
12 Correct 13 ms 25948 KB Output is correct
13 Correct 13 ms 25948 KB Output is correct
14 Correct 11 ms 25692 KB Output is correct
15 Correct 12 ms 26416 KB Output is correct
16 Correct 13 ms 25436 KB Output is correct
17 Correct 12 ms 26012 KB Output is correct
18 Correct 13 ms 26716 KB Output is correct
19 Correct 12 ms 25524 KB Output is correct
20 Correct 13 ms 25944 KB Output is correct
21 Correct 20 ms 27188 KB Output is correct
22 Correct 47 ms 28596 KB Output is correct
23 Correct 31 ms 29644 KB Output is correct
24 Correct 42 ms 33232 KB Output is correct
25 Correct 18 ms 31580 KB Output is correct
26 Correct 37 ms 34148 KB Output is correct
27 Correct 36 ms 30408 KB Output is correct
28 Correct 58 ms 34776 KB Output is correct
29 Correct 32 ms 33604 KB Output is correct
30 Correct 49 ms 31288 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24664 KB Output is correct
2 Correct 13 ms 25436 KB Output is correct
3 Correct 14 ms 25536 KB Output is correct
4 Correct 10 ms 24812 KB Output is correct
5 Correct 10 ms 24944 KB Output is correct
6 Correct 12 ms 25180 KB Output is correct
7 Correct 10 ms 25180 KB Output is correct
8 Correct 11 ms 24924 KB Output is correct
9 Correct 11 ms 25436 KB Output is correct
10 Correct 11 ms 25436 KB Output is correct
11 Correct 233 ms 60140 KB Output is correct
12 Correct 589 ms 116636 KB Output is correct
13 Correct 633 ms 133804 KB Output is correct
14 Correct 668 ms 92968 KB Output is correct
15 Correct 637 ms 92840 KB Output is correct
16 Correct 618 ms 91156 KB Output is correct
17 Correct 575 ms 132324 KB Output is correct
18 Correct 837 ms 131756 KB Output is correct
19 Correct 866 ms 138920 KB Output is correct
20 Correct 451 ms 90024 KB Output is correct
21 Correct 11 ms 25436 KB Output is correct
22 Correct 13 ms 25948 KB Output is correct
23 Correct 13 ms 25948 KB Output is correct
24 Correct 11 ms 25692 KB Output is correct
25 Correct 12 ms 26416 KB Output is correct
26 Correct 13 ms 25436 KB Output is correct
27 Correct 12 ms 26012 KB Output is correct
28 Correct 13 ms 26716 KB Output is correct
29 Correct 12 ms 25524 KB Output is correct
30 Correct 13 ms 25944 KB Output is correct
31 Correct 20 ms 27188 KB Output is correct
32 Correct 47 ms 28596 KB Output is correct
33 Correct 31 ms 29644 KB Output is correct
34 Correct 42 ms 33232 KB Output is correct
35 Correct 18 ms 31580 KB Output is correct
36 Correct 37 ms 34148 KB Output is correct
37 Correct 36 ms 30408 KB Output is correct
38 Correct 58 ms 34776 KB Output is correct
39 Correct 32 ms 33604 KB Output is correct
40 Correct 49 ms 31288 KB Output is correct
41 Correct 166 ms 46348 KB Output is correct
42 Correct 393 ms 102584 KB Output is correct
43 Correct 158 ms 89636 KB Output is correct
44 Correct 488 ms 129192 KB Output is correct
45 Correct 519 ms 121632 KB Output is correct
46 Correct 493 ms 82044 KB Output is correct
47 Correct 655 ms 82976 KB Output is correct
48 Correct 331 ms 111812 KB Output is correct
49 Correct 482 ms 81808 KB Output is correct
50 Correct 550 ms 81208 KB Output is correct
51 Correct 199 ms 84208 KB Output is correct
52 Correct 555 ms 109748 KB Output is correct
53 Correct 327 ms 112308 KB Output is correct
54 Correct 729 ms 118184 KB Output is correct
55 Correct 615 ms 126124 KB Output is correct