oj.uz

Submission #577219

# Submission time Handle Problem Language Result Execution time Memory
577219 2022-06-14T09:35:15 Z AngusWong Parachute rings (IOI12_rings) C++17
0 / 100
 2338 ms 226936 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 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{
		// do sth
	}
	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});
}
 
void dfs(int x, int prev=-1){
	if (!cyc.empty()) return;
	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;
		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;
}
 
int CountCritical() {
	for (int i=0; i<n; i++){
		if (!vis[i]) dfs(i);
	}
	return crit.size();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct
3 Correct 14 ms 24356 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 15 ms 24356 KB Output is correct
6 Correct 21 ms 25036 KB Output is correct
7 Correct 14 ms 24188 KB Output is correct
8 Incorrect 19 ms 24348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 76064 KB Output is correct
2 Correct 1202 ms 93036 KB Output is correct
3 Correct 1260 ms 92212 KB Output is correct
4 Correct 1512 ms 124160 KB Output is correct
5 Correct 1374 ms 137072 KB Output is correct
6 Correct 2338 ms 226936 KB Output is correct
7 Correct 1215 ms 103228 KB Output is correct
8 Correct 1440 ms 125188 KB Output is correct
9 Correct 1526 ms 134328 KB Output is correct
10 Incorrect 1092 ms 143308 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct
3 Correct 14 ms 24356 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 15 ms 24356 KB Output is correct
6 Correct 21 ms 25036 KB Output is correct
7 Correct 14 ms 24188 KB Output is correct
8 Incorrect 19 ms 24348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct
3 Correct 14 ms 24356 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 15 ms 24356 KB Output is correct
6 Correct 21 ms 25036 KB Output is correct
7 Correct 14 ms 24188 KB Output is correct
8 Incorrect 19 ms 24348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct
3 Correct 14 ms 24356 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 15 ms 24356 KB Output is correct
6 Correct 21 ms 25036 KB Output is correct
7 Correct 14 ms 24188 KB Output is correct
8 Incorrect 19 ms 24348 KB Output isn't correct
9 Halted 0 ms 0 KB -