oj.uz

Submission #576057

# Submission time Handle Problem Language Result Execution time Memory
576057 2022-06-12T07:34:43 Z benson1029 Parachute rings (IOI12_rings) C++14
37 / 100
 1490 ms 213160 KB 
#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(cyc[find(x)]>1) GG = 1;
		cyc[find(x)]++;
		if(!GG) dfs(x, y, y);
		for(int i:undolist) vis[i] = false;
		undolist.clear();
	} 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 13 ms 23764 KB Output is correct
2 Correct 15 ms 23892 KB Output is correct
3 Correct 14 ms 23916 KB Output is correct
4 Correct 14 ms 23784 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 16 ms 25044 KB Output is correct
7 Correct 13 ms 23760 KB Output is correct
8 Correct 15 ms 24108 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 15 ms 23980 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 44068 KB Output is correct
2 Correct 718 ms 55072 KB Output is correct
3 Correct 602 ms 55212 KB Output is correct
4 Correct 928 ms 65340 KB Output is correct
5 Correct 970 ms 73664 KB Output is correct
6 Correct 1490 ms 213160 KB Output is correct
7 Correct 547 ms 55316 KB Output is correct
8 Correct 849 ms 60364 KB Output is correct
9 Correct 890 ms 62796 KB Output is correct
10 Correct 1251 ms 86476 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 15 ms 23892 KB Output is correct
3 Correct 14 ms 23916 KB Output is correct
4 Correct 14 ms 23784 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 16 ms 25044 KB Output is correct
7 Correct 13 ms 23760 KB Output is correct
8 Correct 15 ms 24108 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 15 ms 23980 KB Output is correct
11 Correct 13 ms 24000 KB Output is correct
12 Correct 19 ms 24504 KB Output is correct
13 Correct 15 ms 24276 KB Output is correct
14 Incorrect 14 ms 24036 KB Output isn't correct
15 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 15 ms 23892 KB Output is correct
3 Correct 14 ms 23916 KB Output is correct
4 Correct 14 ms 23784 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 16 ms 25044 KB Output is correct
7 Correct 13 ms 23760 KB Output is correct
8 Correct 15 ms 24108 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 15 ms 23980 KB Output is correct
11 Correct 13 ms 24000 KB Output is correct
12 Correct 19 ms 24504 KB Output is correct
13 Correct 15 ms 24276 KB Output is correct
14 Incorrect 14 ms 24036 KB Output isn't correct
15 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 15 ms 23892 KB Output is correct
3 Correct 14 ms 23916 KB Output is correct
4 Correct 14 ms 23784 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 16 ms 25044 KB Output is correct
7 Correct 13 ms 23760 KB Output is correct
8 Correct 15 ms 24108 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 15 ms 23980 KB Output is correct
11 Correct 338 ms 44068 KB Output is correct
12 Correct 718 ms 55072 KB Output is correct
13 Correct 602 ms 55212 KB Output is correct
14 Correct 928 ms 65340 KB Output is correct
15 Correct 970 ms 73664 KB Output is correct
16 Correct 1490 ms 213160 KB Output is correct
17 Correct 547 ms 55316 KB Output is correct
18 Correct 849 ms 60364 KB Output is correct
19 Correct 890 ms 62796 KB Output is correct
20 Correct 1251 ms 86476 KB Output is correct
21 Correct 13 ms 24000 KB Output is correct
22 Correct 19 ms 24504 KB Output is correct
23 Correct 15 ms 24276 KB Output is correct
24 Incorrect 14 ms 24036 KB Output isn't correct
25 Halted 0 ms 0 KB -