oj.uz

Submission #500514

# Submission time Handle Problem Language Result Execution time Memory
500514 2021-12-31T09:35:20 Z sidon Parachute rings (IOI12_rings) C++17
38 / 100
 4000 ms 61820 KB 
#include <bits/stdc++.h>
using namespace std;

vector<array<int, 2>> g;
int N, p;

struct Solver {
	int e[1<<20], d[1<<20] = {};
	int maxDeg = 0, cycle = -1, rem = -1;
	int find(int u){
		return e[u] < 0 ? u : e[u] = find(e[u]);
	}
	void add(int u, int v) {
		
		if(u == rem || v == rem) return;
		maxDeg = max({maxDeg, ++d[u], ++d[v]});
		
		if((u = find(u)) == (v = find(v))) {
			cycle >= 0 ? maxDeg = 3 : cycle = u;
		} else {
			if(e[u] > e[v]) swap(u, v);
			e[u] += e[v], e[v] = u;
		}
	}
	int get() {
		if(maxDeg > 2) return 0;
		return cycle >= 0 ? e[cycle] : N;
	}
} s[5];

void Init(int N_) {
	N = N_;
	s[0].get();
	for(int i = 0; i < 5; i++)
		fill(s[i].e, s[i].e+N, -1);
}

void Link(int A, int B) {
	g.push_back({A, B});
	if(!p) {
		s[0].add(A, B);
		if(s[0].maxDeg > 2) {
			for(int i = 0; i < N; i++)
				if(s[0].d[i] > 2) s[p=1].rem = i;
			for(auto &[u, v] : g) {
				if(u == s[1].rem) s[++p].rem = v;
				if(v == s[1].rem) s[++p].rem = u;
			}
			for(int i = 1; i < 5; i++)
				for(auto &[u, v] : g)
					s[i].add(u, v);
		}
	} else {
		for(int i = 1; i < 5; i++)
			s[i].add(A, B);
	}
}

int CountCritical() {
	int res = 0;
	if(!p) res = abs(s[0].get());
	else {
		for(int i = 1; i < 5; i++)
			res += s[i].get() > 0;
	}
	return res;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20812 KB Output is correct
2 Correct 9 ms 21016 KB Output is correct
3 Correct 10 ms 21060 KB Output is correct
4 Correct 9 ms 20856 KB Output is correct
5 Correct 9 ms 21008 KB Output is correct
6 Correct 10 ms 21068 KB Output is correct
7 Correct 9 ms 20860 KB Output is correct
8 Correct 19 ms 21068 KB Output is correct
9 Correct 10 ms 21008 KB Output is correct
10 Correct 10 ms 21020 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 42060 KB Output is correct
2 Correct 558 ms 53648 KB Output is correct
3 Correct 704 ms 60584 KB Output is correct
4 Correct 331 ms 61708 KB Output is correct
5 Correct 339 ms 61820 KB Output is correct
6 Correct 328 ms 60936 KB Output is correct
7 Correct 658 ms 59768 KB Output is correct
8 Correct 587 ms 59240 KB Output is correct
9 Correct 641 ms 61716 KB Output is correct
10 Execution timed out 4056 ms 60660 KB Time limit exceeded

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20812 KB Output is correct
2 Correct 9 ms 21016 KB Output is correct
3 Correct 10 ms 21060 KB Output is correct
4 Correct 9 ms 20856 KB Output is correct
5 Correct 9 ms 21008 KB Output is correct
6 Correct 10 ms 21068 KB Output is correct
7 Correct 9 ms 20860 KB Output is correct
8 Correct 19 ms 21068 KB Output is correct
9 Correct 10 ms 21008 KB Output is correct
10 Correct 10 ms 21020 KB Output is correct
11 Correct 10 ms 21060 KB Output is correct
12 Correct 11 ms 21328 KB Output is correct
13 Correct 11 ms 21332 KB Output is correct
14 Correct 10 ms 21168 KB Output is correct
15 Correct 13 ms 21444 KB Output is correct
16 Correct 99 ms 21396 KB Output is correct
17 Correct 11 ms 21320 KB Output is correct
18 Correct 11 ms 21600 KB Output is correct
19 Correct 10 ms 21324 KB Output is correct
20 Correct 11 ms 21324 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20812 KB Output is correct
2 Correct 9 ms 21016 KB Output is correct
3 Correct 10 ms 21060 KB Output is correct
4 Correct 9 ms 20856 KB Output is correct
5 Correct 9 ms 21008 KB Output is correct
6 Correct 10 ms 21068 KB Output is correct
7 Correct 9 ms 20860 KB Output is correct
8 Correct 19 ms 21068 KB Output is correct
9 Correct 10 ms 21008 KB Output is correct
10 Correct 10 ms 21020 KB Output is correct
11 Correct 10 ms 21060 KB Output is correct
12 Correct 11 ms 21328 KB Output is correct
13 Correct 11 ms 21332 KB Output is correct
14 Correct 10 ms 21168 KB Output is correct
15 Correct 13 ms 21444 KB Output is correct
16 Correct 99 ms 21396 KB Output is correct
17 Correct 11 ms 21320 KB Output is correct
18 Correct 11 ms 21600 KB Output is correct
19 Correct 10 ms 21324 KB Output is correct
20 Correct 11 ms 21324 KB Output is correct
21 Correct 18 ms 22728 KB Output is correct
22 Correct 26 ms 23848 KB Output is correct
23 Correct 31 ms 24540 KB Output is correct
24 Correct 35 ms 24172 KB Output is correct
25 Correct 19 ms 23244 KB Output is correct
26 Correct 34 ms 24360 KB Output is correct
27 Execution timed out 4037 ms 24816 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20812 KB Output is correct
2 Correct 9 ms 21016 KB Output is correct
3 Correct 10 ms 21060 KB Output is correct
4 Correct 9 ms 20856 KB Output is correct
5 Correct 9 ms 21008 KB Output is correct
6 Correct 10 ms 21068 KB Output is correct
7 Correct 9 ms 20860 KB Output is correct
8 Correct 19 ms 21068 KB Output is correct
9 Correct 10 ms 21008 KB Output is correct
10 Correct 10 ms 21020 KB Output is correct
11 Correct 160 ms 42060 KB Output is correct
12 Correct 558 ms 53648 KB Output is correct
13 Correct 704 ms 60584 KB Output is correct
14 Correct 331 ms 61708 KB Output is correct
15 Correct 339 ms 61820 KB Output is correct
16 Correct 328 ms 60936 KB Output is correct
17 Correct 658 ms 59768 KB Output is correct
18 Correct 587 ms 59240 KB Output is correct
19 Correct 641 ms 61716 KB Output is correct
20 Execution timed out 4056 ms 60660 KB Time limit exceeded