Submission #576052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
576052	2022-06-12T07:05:48 Z	benson1029	Parachute rings (IOI12_rings)	C++14	20 / 100	4000 ms	262144 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;
int dsu[1000005];
int cyc[1000005];
bool vis[1000005];
int pre[1000005];
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;
		set<int> tmp;
		while(ptr != -1) {
			tmp.insert(ptr);
			ptr = pre[ptr];
		}
		setintersection(tmp);
		return;
	}
	for(int i:edg[x]) {
		if(i==p) continue;
		dfs(i, x, tar);
	}
}

void merge(int x, int y) {
	if(find(x)==find(y)) {
		if(cyc[find(x)]) GG = 1;
		cyc[find(x)] = true;
		dfs(x, -1, y);
	} else {
		if(cyc[find(y)]) cyc[find(x)] = true;
		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) {
	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	15 ms	23788 KB	Output is correct
2	Correct	14 ms	24020 KB	Output is correct
3	Correct	14 ms	24020 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	17 ms	25204 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	16 ms	24204 KB	Output is correct
9	Correct	16 ms	24020 KB	Output is correct
10	Correct	18 ms	24044 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	332 ms	46200 KB	Output is correct
2	Correct	671 ms	56012 KB	Output is correct
3	Execution timed out	4083 ms	182928 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	14 ms	24020 KB	Output is correct
3	Correct	14 ms	24020 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	17 ms	25204 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	16 ms	24204 KB	Output is correct
9	Correct	16 ms	24020 KB	Output is correct
10	Correct	18 ms	24044 KB	Output is correct
11	Runtime error	478 ms	262144 KB	Execution killed with signal 9
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	14 ms	24020 KB	Output is correct
3	Correct	14 ms	24020 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	17 ms	25204 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	16 ms	24204 KB	Output is correct
9	Correct	16 ms	24020 KB	Output is correct
10	Correct	18 ms	24044 KB	Output is correct
11	Runtime error	478 ms	262144 KB	Execution killed with signal 9
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	14 ms	24020 KB	Output is correct
3	Correct	14 ms	24020 KB	Output is correct
4	Correct	13 ms	23892 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	17 ms	25204 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	16 ms	24204 KB	Output is correct
9	Correct	16 ms	24020 KB	Output is correct
10	Correct	18 ms	24044 KB	Output is correct
11	Correct	332 ms	46200 KB	Output is correct
12	Correct	671 ms	56012 KB	Output is correct
13	Execution timed out	4083 ms	182928 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-