oj.uz

Submission #576059

# Submission time Handle Problem Language Result Execution time Memory
576059 2022-06-12T07:37:32 Z benson1029 Parachute rings (IOI12_rings) C++14
37 / 100
 1595 ms 213264 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();
		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 12 ms 23764 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 14 ms 23960 KB Output is correct
4 Correct 14 ms 23848 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 20 ms 25036 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 18 ms 24172 KB Output is correct
9 Correct 17 ms 24036 KB Output is correct
10 Correct 14 ms 24036 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 44068 KB Output is correct
2 Correct 773 ms 55020 KB Output is correct
3 Correct 559 ms 55168 KB Output is correct
4 Correct 982 ms 65416 KB Output is correct
5 Correct 998 ms 73760 KB Output is correct
6 Correct 1595 ms 213264 KB Output is correct
7 Correct 547 ms 55312 KB Output is correct
8 Correct 877 ms 60304 KB Output is correct
9 Correct 960 ms 62884 KB Output is correct
10 Correct 1299 ms 86568 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 14 ms 23960 KB Output is correct
4 Correct 14 ms 23848 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 20 ms 25036 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 18 ms 24172 KB Output is correct
9 Correct 17 ms 24036 KB Output is correct
10 Correct 14 ms 24036 KB Output is correct
11 Correct 14 ms 24108 KB Output is correct
12 Correct 16 ms 24516 KB Output is correct
13 Correct 16 ms 24292 KB Output is correct
14 Incorrect 14 ms 24020 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 14 ms 23960 KB Output is correct
4 Correct 14 ms 23848 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 20 ms 25036 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 18 ms 24172 KB Output is correct
9 Correct 17 ms 24036 KB Output is correct
10 Correct 14 ms 24036 KB Output is correct
11 Correct 14 ms 24108 KB Output is correct
12 Correct 16 ms 24516 KB Output is correct
13 Correct 16 ms 24292 KB Output is correct
14 Incorrect 14 ms 24020 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 14 ms 23960 KB Output is correct
4 Correct 14 ms 23848 KB Output is correct
5 Correct 14 ms 24404 KB Output is correct
6 Correct 20 ms 25036 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 18 ms 24172 KB Output is correct
9 Correct 17 ms 24036 KB Output is correct
10 Correct 14 ms 24036 KB Output is correct
11 Correct 334 ms 44068 KB Output is correct
12 Correct 773 ms 55020 KB Output is correct
13 Correct 559 ms 55168 KB Output is correct
14 Correct 982 ms 65416 KB Output is correct
15 Correct 998 ms 73760 KB Output is correct
16 Correct 1595 ms 213264 KB Output is correct
17 Correct 547 ms 55312 KB Output is correct
18 Correct 877 ms 60304 KB Output is correct
19 Correct 960 ms 62884 KB Output is correct
20 Correct 1299 ms 86568 KB Output is correct
21 Correct 14 ms 24108 KB Output is correct
22 Correct 16 ms 24516 KB Output is correct
23 Correct 16 ms 24292 KB Output is correct
24 Incorrect 14 ms 24020 KB Output isn't correct
25 Halted 0 ms 0 KB -