Submission #576054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
576054	2022-06-12T07:19:06 Z	benson1029	Parachute rings (IOI12_rings)	C++14	37 / 100	1444 ms	208220 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;

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;
	if(x==tar) {
		int ptr = tar;
		tmp.clear();
		while(ptr != -1) {
			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(cyc[find(x)]>1) GG = 1;
		cyc[find(x)]++;
		if(!GG) dfs(x, -1, y);
	} 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;
	merge(A, B);
	edg[A].push_back(B);
	edg[B].push_back(A);
	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	13 ms	23764 KB	Output is correct
2	Correct	14 ms	24000 KB	Output is correct
3	Correct	16 ms	24092 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	15 ms	25044 KB	Output is correct
7	Correct	12 ms	23800 KB	Output is correct
8	Correct	15 ms	24148 KB	Output is correct
9	Correct	17 ms	23960 KB	Output is correct
10	Correct	15 ms	24088 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	333 ms	44448 KB	Output is correct
2	Correct	657 ms	55316 KB	Output is correct
3	Correct	501 ms	58240 KB	Output is correct
4	Correct	886 ms	69944 KB	Output is correct
5	Correct	890 ms	77848 KB	Output is correct
6	Correct	1444 ms	208220 KB	Output is correct
7	Correct	527 ms	59388 KB	Output is correct
8	Correct	819 ms	64884 KB	Output is correct
9	Correct	868 ms	67308 KB	Output is correct
10	Correct	1251 ms	89152 KB	Output is correct

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23764 KB	Output is correct
2	Correct	14 ms	24000 KB	Output is correct
3	Correct	16 ms	24092 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	15 ms	25044 KB	Output is correct
7	Correct	12 ms	23800 KB	Output is correct
8	Correct	15 ms	24148 KB	Output is correct
9	Correct	17 ms	23960 KB	Output is correct
10	Correct	15 ms	24088 KB	Output is correct
11	Incorrect	16 ms	24020 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23764 KB	Output is correct
2	Correct	14 ms	24000 KB	Output is correct
3	Correct	16 ms	24092 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	15 ms	25044 KB	Output is correct
7	Correct	12 ms	23800 KB	Output is correct
8	Correct	15 ms	24148 KB	Output is correct
9	Correct	17 ms	23960 KB	Output is correct
10	Correct	15 ms	24088 KB	Output is correct
11	Incorrect	16 ms	24020 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23764 KB	Output is correct
2	Correct	14 ms	24000 KB	Output is correct
3	Correct	16 ms	24092 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	15 ms	25044 KB	Output is correct
7	Correct	12 ms	23800 KB	Output is correct
8	Correct	15 ms	24148 KB	Output is correct
9	Correct	17 ms	23960 KB	Output is correct
10	Correct	15 ms	24088 KB	Output is correct
11	Correct	333 ms	44448 KB	Output is correct
12	Correct	657 ms	55316 KB	Output is correct
13	Correct	501 ms	58240 KB	Output is correct
14	Correct	886 ms	69944 KB	Output is correct
15	Correct	890 ms	77848 KB	Output is correct
16	Correct	1444 ms	208220 KB	Output is correct
17	Correct	527 ms	59388 KB	Output is correct
18	Correct	819 ms	64884 KB	Output is correct
19	Correct	868 ms	67308 KB	Output is correct
20	Correct	1251 ms	89152 KB	Output is correct
21	Incorrect	16 ms	24020 KB	Output isn't correct
22	Halted	0 ms	0 KB	-