Submission #229615

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
229615	2020-05-05T10:46:30 Z	maruii	Parachute rings (IOI12_rings)	C++14	20 / 100	4000 ms	88544 KB

rings

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

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


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 (vis[x] || edge[x].size() < 3) return;
	//vis[x] = 1;
	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 = x; j != i; j = 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	19 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	22 ms	24320 KB	Output is correct
6	Correct	26 ms	24704 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	21 ms	24192 KB	Output is correct
9	Correct	21 ms	24320 KB	Output is correct
10	Correct	21 ms	24320 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	526 ms	50536 KB	Output is correct
2	Correct	938 ms	64720 KB	Output is correct
3	Correct	332 ms	53472 KB	Output is correct
4	Correct	1445 ms	86760 KB	Output is correct
5	Execution timed out	4089 ms	88544 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 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	22 ms	24320 KB	Output is correct
6	Correct	26 ms	24704 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	21 ms	24192 KB	Output is correct
9	Correct	21 ms	24320 KB	Output is correct
10	Correct	21 ms	24320 KB	Output is correct
11	Incorrect	27 ms	24192 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 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	22 ms	24320 KB	Output is correct
6	Correct	26 ms	24704 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	21 ms	24192 KB	Output is correct
9	Correct	21 ms	24320 KB	Output is correct
10	Correct	21 ms	24320 KB	Output is correct
11	Incorrect	27 ms	24192 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 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	22 ms	24320 KB	Output is correct
6	Correct	26 ms	24704 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	21 ms	24192 KB	Output is correct
9	Correct	21 ms	24320 KB	Output is correct
10	Correct	21 ms	24320 KB	Output is correct
11	Correct	526 ms	50536 KB	Output is correct
12	Correct	938 ms	64720 KB	Output is correct
13	Correct	332 ms	53472 KB	Output is correct
14	Correct	1445 ms	86760 KB	Output is correct
15	Execution timed out	4089 ms	88544 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-