Submission #229617

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
229617	2020-05-05T10:55:00 Z	maruii	Parachute rings (IOI12_rings)	C++14	20 / 100	4000 ms	75368 KB

rings

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

int N, flag, cyc, up[1000005], par[1000005];
vector<int> edge[1000005], ans;


int fnd(int x) { return up[x] == x ? x : up[x] = fnd(up[x]); }
void Init(int N_) {
	N = N_;
	for (int i = 0; i < N; ++i) {
		up[i] = i;
		ans.push_back(i);
	}
}

void update(int x) {
	if (edge[x].size() < 3) return;
	vector<int> v;
	for (auto i : ans) {
		if (i == x) v.push_back(i);
		else if (edge[x].size() < 4) for (auto j : edge[x]) if (i == j) {
			v.push_back(i);
			break;
		}
	}
	ans = v;
}

void Link(int a, int b) {
	if (ans.empty()) return;
	edge[a].push_back(b);
	edge[b].push_back(a);
	update(a);
	update(b);
}

bool vi[1000005];
int dep[1000005];
void dfs(int x, int p) {
	vi[x] = 1;
	for (auto i : edge[x]) if (i != p) {
		if (vi[i]) {
			if (dep[i] < dep[x]) {
				vector<int> u, v;
				u.push_back(i);
				for (int j = fnd(x); j != fnd(i); j = fnd(par[j])) {
					up[j] = fnd(par[j]);
					u.push_back(j);
				}

				for (auto i : ans) {
					for (auto j : u) if (i == j) {
						v.push_back(i);
						break;
					}
				}
				ans = v;

			}
			continue;
		}
		par[i] = x;
		dep[i] = dep[x] + 1;
		dfs(i, x);
	}
}

int CountCritical() {
	for (int i = 0; i < N; ++i) vi[i] = 0;
	for (int i = 0; i < N; ++i) if (!vi[i]) {
		dep[i] = 0; 
		dfs(i, i);
	}
	return ans.size();
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	20 ms	24064 KB	Output is correct
3	Correct	21 ms	24192 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	21 ms	24320 KB	Output is correct
6	Correct	26 ms	24832 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	22 ms	24192 KB	Output is correct
9	Correct	21 ms	24320 KB	Output is correct
10	Correct	21 ms	24192 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	512 ms	48844 KB	Output is correct
2	Correct	938 ms	62944 KB	Output is correct
3	Correct	344 ms	40800 KB	Output is correct
4	Correct	1397 ms	73188 KB	Output is correct
5	Execution timed out	4096 ms	75368 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	20 ms	24064 KB	Output is correct
3	Correct	21 ms	24192 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	21 ms	24320 KB	Output is correct
6	Correct	26 ms	24832 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	22 ms	24192 KB	Output is correct
9	Correct	21 ms	24320 KB	Output is correct
10	Correct	21 ms	24192 KB	Output is correct
11	Incorrect	24 ms	24064 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	20 ms	24064 KB	Output is correct
3	Correct	21 ms	24192 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	21 ms	24320 KB	Output is correct
6	Correct	26 ms	24832 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	22 ms	24192 KB	Output is correct
9	Correct	21 ms	24320 KB	Output is correct
10	Correct	21 ms	24192 KB	Output is correct
11	Incorrect	24 ms	24064 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	20 ms	24064 KB	Output is correct
3	Correct	21 ms	24192 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	21 ms	24320 KB	Output is correct
6	Correct	26 ms	24832 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	22 ms	24192 KB	Output is correct
9	Correct	21 ms	24320 KB	Output is correct
10	Correct	21 ms	24192 KB	Output is correct
11	Correct	512 ms	48844 KB	Output is correct
12	Correct	938 ms	62944 KB	Output is correct
13	Correct	344 ms	40800 KB	Output is correct
14	Correct	1397 ms	73188 KB	Output is correct
15	Execution timed out	4096 ms	75368 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-