oj.uz

Submission #577221

# Submission time Handle Problem Language Result Execution time Memory
577221 2022-06-14T09:36:45 Z AngusWong Parachute rings (IOI12_rings) C++17
37 / 100
 2416 ms 215220 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){
	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;
}
 
int CountCritical() {
	for (int i=0; i<n; i++){
		if (!vis[i]) dfs(i);
	}
	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 24260 KB Output is correct
3 Correct 14 ms 24276 KB Output is correct
4 Correct 12 ms 23892 KB Output is correct
5 Correct 15 ms 24400 KB Output is correct
6 Correct 18 ms 25008 KB Output is correct
7 Correct 13 ms 24108 KB Output is correct
8 Correct 15 ms 24372 KB Output is correct
9 Correct 15 ms 24604 KB Output is correct
10 Correct 15 ms 24380 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 74792 KB Output is correct
2 Correct 1166 ms 91660 KB Output is correct
3 Correct 1432 ms 123444 KB Output is correct
4 Correct 1530 ms 122788 KB Output is correct
5 Correct 1530 ms 125472 KB Output is correct
6 Correct 2416 ms 215220 KB Output is correct
7 Correct 1409 ms 120080 KB Output is correct
8 Correct 1417 ms 112852 KB Output is correct
9 Correct 1524 ms 122820 KB Output is correct
10 Correct 1329 ms 134120 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 24260 KB Output is correct
3 Correct 14 ms 24276 KB Output is correct
4 Correct 12 ms 23892 KB Output is correct
5 Correct 15 ms 24400 KB Output is correct
6 Correct 18 ms 25008 KB Output is correct
7 Correct 13 ms 24108 KB Output is correct
8 Correct 15 ms 24372 KB Output is correct
9 Correct 15 ms 24604 KB Output is correct
10 Correct 15 ms 24380 KB Output is correct
11 Incorrect 14 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 24260 KB Output is correct
3 Correct 14 ms 24276 KB Output is correct
4 Correct 12 ms 23892 KB Output is correct
5 Correct 15 ms 24400 KB Output is correct
6 Correct 18 ms 25008 KB Output is correct
7 Correct 13 ms 24108 KB Output is correct
8 Correct 15 ms 24372 KB Output is correct
9 Correct 15 ms 24604 KB Output is correct
10 Correct 15 ms 24380 KB Output is correct
11 Incorrect 14 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 24260 KB Output is correct
3 Correct 14 ms 24276 KB Output is correct
4 Correct 12 ms 23892 KB Output is correct
5 Correct 15 ms 24400 KB Output is correct
6 Correct 18 ms 25008 KB Output is correct
7 Correct 13 ms 24108 KB Output is correct
8 Correct 15 ms 24372 KB Output is correct
9 Correct 15 ms 24604 KB Output is correct
10 Correct 15 ms 24380 KB Output is correct
11 Correct 609 ms 74792 KB Output is correct
12 Correct 1166 ms 91660 KB Output is correct
13 Correct 1432 ms 123444 KB Output is correct
14 Correct 1530 ms 122788 KB Output is correct
15 Correct 1530 ms 125472 KB Output is correct
16 Correct 2416 ms 215220 KB Output is correct
17 Correct 1409 ms 120080 KB Output is correct
18 Correct 1417 ms 112852 KB Output is correct
19 Correct 1524 ms 122820 KB Output is correct
20 Correct 1329 ms 134120 KB Output is correct
21 Incorrect 14 ms 24276 KB Output isn't correct
22 Halted 0 ms 0 KB -