Submission #576091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
576091	2022-06-12T10:00:01 Z	benson1029	Parachute rings (IOI12_rings)	C++14	55 / 100	1558 ms	214468 KB

rings

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

vector<int> edg[1000005];
int DEG3 = -1;
int DEG4 = -1;
bool choicesToggle = false;
set<int> choices, tmp;
int dsu[1000005];
int cyc[1000005];
bool vis[1000005];
int pre[1000005];
int cyccnt = 0;
int GG = 0;
vector<int> undolist;

int find(int x) {
	if(dsu[x]==x)return x;
	return dsu[x] = find(dsu[x]);
}

void setintersection(set<int> tmp) {
	if(!choicesToggle) {
		choicesToggle = true;
		choices = tmp;
		return;
	}
	set<int> tmp2;
	for(int i:tmp) {
		if(choices.find(i)!=choices.end()) {
			tmp2.insert(i);
		}
	}
	choices = tmp2;
}

void dfs(int x, int p, int tar) {
	vis[x] = true;
	pre[x] = p;
	undolist.push_back(x);
	if(x==tar) {
		int ptr = pre[tar];
		tmp.clear();
		tmp.insert(tar);
		while(ptr != tar) {
			tmp.insert(ptr);
			ptr = pre[ptr];
		}
		setintersection(tmp);
		return;
	}
	for(int i:edg[x]) {
		if(i==p) continue;
		if(!vis[i]) dfs(i, x, tar);
	}
}

void merge(int x, int y) {
	if(find(x)==find(y)) {
		if(N>20000&&cyc[find(x)]>1) GG = 1;
		cyc[find(x)]++;
		if(!GG) dfs(x, y, y);
		for(int i:undolist) vis[i] = false;
		undolist.clear();
		if(cyc[find(x)]==2) {
			tmp.clear();
			for(int i:choices) {
				if(edg[i].size()>=3) tmp.insert(i);
			}
			choices = tmp;
		}
	} else {
		cyc[find(x)] += cyc[find(y)];
		dsu[find(y)] = find(x);
	}
}

void Init(int N_) {
	N = N_;
	for(int i=0; i<N; i++) dsu[i] = i;
}


void Link(int A, int B) {
	if(GG) return;
	edg[A].push_back(B);
	edg[B].push_back(A);
	merge(A, B);
	if(edg[A].size()==4) setintersection({A});
	else if(edg[A].size()==3) setintersection({A, edg[A][0], edg[A][1], edg[A][2]});
	if(edg[B].size()==4) setintersection({B});
	else if(edg[B].size()==3) setintersection({B, edg[B][0], edg[B][1], edg[B][2]});
}

int CountCritical() {
	if(GG) return 0;
	if(!choicesToggle) return N;
	else return choices.size();
}

Subtask #1
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23764 KB	Output is correct
2	Correct	15 ms	23892 KB	Output is correct
3	Correct	16 ms	24020 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	17 ms	24404 KB	Output is correct
6	Correct	18 ms	25044 KB	Output is correct
7	Correct	13 ms	23804 KB	Output is correct
8	Correct	16 ms	24112 KB	Output is correct
9	Correct	15 ms	24020 KB	Output is correct
10	Correct	14 ms	24032 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	44252 KB	Output is correct
2	Correct	790 ms	55016 KB	Output is correct
3	Correct	587 ms	56348 KB	Output is correct
4	Correct	1002 ms	66696 KB	Output is correct
5	Correct	1055 ms	74988 KB	Output is correct
6	Correct	1558 ms	214468 KB	Output is correct
7	Correct	581 ms	57024 KB	Output is correct
8	Correct	967 ms	61948 KB	Output is correct
9	Correct	1041 ms	64384 KB	Output is correct
10	Correct	1407 ms	87940 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23764 KB	Output is correct
2	Correct	15 ms	23892 KB	Output is correct
3	Correct	16 ms	24020 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	17 ms	24404 KB	Output is correct
6	Correct	18 ms	25044 KB	Output is correct
7	Correct	13 ms	23804 KB	Output is correct
8	Correct	16 ms	24112 KB	Output is correct
9	Correct	15 ms	24020 KB	Output is correct
10	Correct	14 ms	24032 KB	Output is correct
11	Correct	16 ms	24148 KB	Output is correct
12	Correct	174 ms	25804 KB	Output is correct
13	Correct	388 ms	25964 KB	Output is correct
14	Correct	179 ms	24148 KB	Output is correct
15	Correct	266 ms	24332 KB	Output is correct
16	Correct	23 ms	24496 KB	Output is correct
17	Correct	17 ms	24404 KB	Output is correct
18	Correct	18 ms	24540 KB	Output is correct
19	Correct	18 ms	24384 KB	Output is correct
20	Correct	18 ms	24276 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23764 KB	Output is correct
2	Correct	15 ms	23892 KB	Output is correct
3	Correct	16 ms	24020 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	17 ms	24404 KB	Output is correct
6	Correct	18 ms	25044 KB	Output is correct
7	Correct	13 ms	23804 KB	Output is correct
8	Correct	16 ms	24112 KB	Output is correct
9	Correct	15 ms	24020 KB	Output is correct
10	Correct	14 ms	24032 KB	Output is correct
11	Correct	16 ms	24148 KB	Output is correct
12	Correct	174 ms	25804 KB	Output is correct
13	Correct	388 ms	25964 KB	Output is correct
14	Correct	179 ms	24148 KB	Output is correct
15	Correct	266 ms	24332 KB	Output is correct
16	Correct	23 ms	24496 KB	Output is correct
17	Correct	17 ms	24404 KB	Output is correct
18	Correct	18 ms	24540 KB	Output is correct
19	Correct	18 ms	24384 KB	Output is correct
20	Correct	18 ms	24276 KB	Output is correct
21	Correct	28 ms	25292 KB	Output is correct
22	Correct	37 ms	26188 KB	Output is correct
23	Correct	45 ms	26772 KB	Output is correct
24	Incorrect	34 ms	25696 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23764 KB	Output is correct
2	Correct	15 ms	23892 KB	Output is correct
3	Correct	16 ms	24020 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	17 ms	24404 KB	Output is correct
6	Correct	18 ms	25044 KB	Output is correct
7	Correct	13 ms	23804 KB	Output is correct
8	Correct	16 ms	24112 KB	Output is correct
9	Correct	15 ms	24020 KB	Output is correct
10	Correct	14 ms	24032 KB	Output is correct
11	Correct	416 ms	44252 KB	Output is correct
12	Correct	790 ms	55016 KB	Output is correct
13	Correct	587 ms	56348 KB	Output is correct
14	Correct	1002 ms	66696 KB	Output is correct
15	Correct	1055 ms	74988 KB	Output is correct
16	Correct	1558 ms	214468 KB	Output is correct
17	Correct	581 ms	57024 KB	Output is correct
18	Correct	967 ms	61948 KB	Output is correct
19	Correct	1041 ms	64384 KB	Output is correct
20	Correct	1407 ms	87940 KB	Output is correct
21	Correct	16 ms	24148 KB	Output is correct
22	Correct	174 ms	25804 KB	Output is correct
23	Correct	388 ms	25964 KB	Output is correct
24	Correct	179 ms	24148 KB	Output is correct
25	Correct	266 ms	24332 KB	Output is correct
26	Correct	23 ms	24496 KB	Output is correct
27	Correct	17 ms	24404 KB	Output is correct
28	Correct	18 ms	24540 KB	Output is correct
29	Correct	18 ms	24384 KB	Output is correct
30	Correct	18 ms	24276 KB	Output is correct
31	Correct	28 ms	25292 KB	Output is correct
32	Correct	37 ms	26188 KB	Output is correct
33	Correct	45 ms	26772 KB	Output is correct
34	Incorrect	34 ms	25696 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

Submission #576091

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
0 / 14.0

Subtask #5
0 / 31.0