oj.uz

Submission #577224

# Submission time Handle Problem Language Result Execution time Memory
577224 2022-06-14T09:47:08 Z AngusWong Parachute rings (IOI12_rings) C++17
37 / 100
 2288 ms 215244 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N=1e6+1;
int n, cnt[N], dsu[N], sz[N];
vector<int> v[N], v2;
set<int> crit, tmp;
int vis[N], par[N];
vector<int> cyc;
 
int find(int x){
	return dsu[x]==x? x: dsu[x]=find(dsu[x]);
}
 
void join(int x, int y){
	x=find(x), y=find(y);
	sz[y]+=sz[x];
	dsu[x]=y;
}
 
void Init(int N_) {
	n=N_;
	for (int i=0; i<n; i++){
		cnt[i]=0;
		dsu[i]=i, sz[i]=1;
		v[i].clear();
		crit.insert(i);
		vis[i]=0, par[i]=-1;
	}
	cyc.clear();
}
 
void setcrit(vector<int> v){
	tmp.clear();
	for (int i: v){
		if (crit.find(i)!=crit.end()) tmp.insert(i);
	}
	crit=tmp;
}

void dfs(int x, int prev=-1){
	vis[x]=1, par[x]=prev;
	for (int i: v[x]){
		if (!vis[i]){
			dfs(i, x);
			continue;
		}
		if (i==prev || vis[i]==2) continue;
		if (!cyc.empty()){
			crit.clear();
			continue;
		}
		int t=x;
		cyc.push_back(i);
		while (t!=i){
			cyc.push_back(t);
			t=par[t];
			assert(t!=-1);
		}
		setcrit(cyc);
	}
	vis[x]=2;
}

void Link(int A, int B) {
	cnt[A]=min(cnt[A]+1, 4), cnt[B]=min(cnt[B]+1, 4);
	v[A].push_back(B);
	v[B].push_back(A);
	if (find(A)!=find(B)) join(A, B);
	else{
		if (!cyc.empty()) crit.clear();
		else dfs(A);
	}
	if (cnt[A]==3){
		v2=v[A];
		v2.push_back(A);
		setcrit(v2);
	}else if (cnt[A]==4) setcrit({A});
	if (cnt[B]==3){
		v2=v[B];
		v2.push_back(B);
		setcrit(v2);
	}else if (cnt[B]==4) setcrit({B});
}
 
int CountCritical() {
	return crit.size();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24156 KB Output is correct
3 Correct 15 ms 24288 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 16 ms 24428 KB Output is correct
6 Correct 19 ms 24960 KB Output is correct
7 Correct 15 ms 24148 KB Output is correct
8 Correct 13 ms 24148 KB Output is correct
9 Correct 15 ms 24296 KB Output is correct
10 Correct 15 ms 24276 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 74672 KB Output is correct
2 Correct 979 ms 91056 KB Output is correct
3 Correct 1268 ms 90848 KB Output is correct
4 Correct 1233 ms 121668 KB Output is correct
5 Correct 1301 ms 125592 KB Output is correct
6 Correct 2288 ms 215244 KB Output is correct
7 Correct 1170 ms 90960 KB Output is correct
8 Correct 1162 ms 112316 KB Output is correct
9 Correct 1215 ms 120700 KB Output is correct
10 Correct 910 ms 120344 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 14 ms 24156 KB Output is correct
3 Correct 15 ms 24288 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 16 ms 24428 KB Output is correct
6 Correct 19 ms 24960 KB Output is correct
7 Correct 15 ms 24148 KB Output is correct
8 Correct 13 ms 24148 KB Output is correct
9 Correct 15 ms 24296 KB Output is correct
10 Correct 15 ms 24276 KB Output is correct
11 Incorrect 15 ms 24276 KB Output isn't correct
12 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 14 ms 24156 KB Output is correct
3 Correct 15 ms 24288 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 16 ms 24428 KB Output is correct
6 Correct 19 ms 24960 KB Output is correct
7 Correct 15 ms 24148 KB Output is correct
8 Correct 13 ms 24148 KB Output is correct
9 Correct 15 ms 24296 KB Output is correct
10 Correct 15 ms 24276 KB Output is correct
11 Incorrect 15 ms 24276 KB Output isn't correct
12 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 14 ms 24156 KB Output is correct
3 Correct 15 ms 24288 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 16 ms 24428 KB Output is correct
6 Correct 19 ms 24960 KB Output is correct
7 Correct 15 ms 24148 KB Output is correct
8 Correct 13 ms 24148 KB Output is correct
9 Correct 15 ms 24296 KB Output is correct
10 Correct 15 ms 24276 KB Output is correct
11 Correct 482 ms 74672 KB Output is correct
12 Correct 979 ms 91056 KB Output is correct
13 Correct 1268 ms 90848 KB Output is correct
14 Correct 1233 ms 121668 KB Output is correct
15 Correct 1301 ms 125592 KB Output is correct
16 Correct 2288 ms 215244 KB Output is correct
17 Correct 1170 ms 90960 KB Output is correct
18 Correct 1162 ms 112316 KB Output is correct
19 Correct 1215 ms 120700 KB Output is correct
20 Correct 910 ms 120344 KB Output is correct
21 Incorrect 15 ms 24276 KB Output isn't correct
22 Halted 0 ms 0 KB -