oj.uz

Submission #576055

# Submission time Handle Problem Language Result Execution time Memory
576055 2022-06-12T07:21:17 Z benson1029 Parachute rings (IOI12_rings) C++14
37 / 100
 1442 ms 205608 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 = 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);
		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;
	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 12 ms 23764 KB Output is correct
2 Correct 17 ms 23948 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 13 ms 23776 KB Output is correct
5 Correct 14 ms 24424 KB Output is correct
6 Correct 16 ms 25044 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 24120 KB Output is correct
9 Correct 12 ms 24020 KB Output is correct
10 Correct 14 ms 23932 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 44192 KB Output is correct
2 Correct 706 ms 55320 KB Output is correct
3 Correct 533 ms 55160 KB Output is correct
4 Correct 870 ms 65536 KB Output is correct
5 Correct 858 ms 73332 KB Output is correct
6 Correct 1442 ms 205608 KB Output is correct
7 Correct 509 ms 55408 KB Output is correct
8 Correct 815 ms 60380 KB Output is correct
9 Correct 865 ms 62924 KB Output is correct
10 Correct 1239 ms 85264 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 17 ms 23948 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 13 ms 23776 KB Output is correct
5 Correct 14 ms 24424 KB Output is correct
6 Correct 16 ms 25044 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 24120 KB Output is correct
9 Correct 12 ms 24020 KB Output is correct
10 Correct 14 ms 23932 KB Output is correct
11 Correct 14 ms 24020 KB Output is correct
12 Correct 16 ms 24532 KB Output is correct
13 Correct 16 ms 24328 KB Output is correct
14 Incorrect 14 ms 24132 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 17 ms 23948 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 13 ms 23776 KB Output is correct
5 Correct 14 ms 24424 KB Output is correct
6 Correct 16 ms 25044 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 24120 KB Output is correct
9 Correct 12 ms 24020 KB Output is correct
10 Correct 14 ms 23932 KB Output is correct
11 Correct 14 ms 24020 KB Output is correct
12 Correct 16 ms 24532 KB Output is correct
13 Correct 16 ms 24328 KB Output is correct
14 Incorrect 14 ms 24132 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 17 ms 23948 KB Output is correct
3 Correct 15 ms 24020 KB Output is correct
4 Correct 13 ms 23776 KB Output is correct
5 Correct 14 ms 24424 KB Output is correct
6 Correct 16 ms 25044 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 24120 KB Output is correct
9 Correct 12 ms 24020 KB Output is correct
10 Correct 14 ms 23932 KB Output is correct
11 Correct 345 ms 44192 KB Output is correct
12 Correct 706 ms 55320 KB Output is correct
13 Correct 533 ms 55160 KB Output is correct
14 Correct 870 ms 65536 KB Output is correct
15 Correct 858 ms 73332 KB Output is correct
16 Correct 1442 ms 205608 KB Output is correct
17 Correct 509 ms 55408 KB Output is correct
18 Correct 815 ms 60380 KB Output is correct
19 Correct 865 ms 62924 KB Output is correct
20 Correct 1239 ms 85264 KB Output is correct
21 Correct 14 ms 24020 KB Output is correct
22 Correct 16 ms 24532 KB Output is correct
23 Correct 16 ms 24328 KB Output is correct
24 Incorrect 14 ms 24132 KB Output isn't correct
25 Halted 0 ms 0 KB -