oj.uz

Submission #577191

# Submission time Handle Problem Language Result Execution time Memory
577191 2022-06-14T08:56:06 Z AngusWong Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 105588 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;
		int t=x;
		cyc.clear();
		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 14 ms 23780 KB Output is correct
2 Correct 14 ms 24248 KB Output is correct
3 Correct 14 ms 24356 KB Output is correct
4 Correct 12 ms 23936 KB Output is correct
5 Correct 15 ms 24356 KB Output is correct
6 Correct 16 ms 25052 KB Output is correct
7 Correct 14 ms 24124 KB Output is correct
8 Correct 14 ms 24404 KB Output is correct
9 Correct 15 ms 24532 KB Output is correct
10 Correct 14 ms 24456 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 75088 KB Output is correct
2 Correct 1184 ms 92000 KB Output is correct
3 Execution timed out 4045 ms 105588 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23780 KB Output is correct
2 Correct 14 ms 24248 KB Output is correct
3 Correct 14 ms 24356 KB Output is correct
4 Correct 12 ms 23936 KB Output is correct
5 Correct 15 ms 24356 KB Output is correct
6 Correct 16 ms 25052 KB Output is correct
7 Correct 14 ms 24124 KB Output is correct
8 Correct 14 ms 24404 KB Output is correct
9 Correct 15 ms 24532 KB Output is correct
10 Correct 14 ms 24456 KB Output is correct
11 Incorrect 13 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 14 ms 23780 KB Output is correct
2 Correct 14 ms 24248 KB Output is correct
3 Correct 14 ms 24356 KB Output is correct
4 Correct 12 ms 23936 KB Output is correct
5 Correct 15 ms 24356 KB Output is correct
6 Correct 16 ms 25052 KB Output is correct
7 Correct 14 ms 24124 KB Output is correct
8 Correct 14 ms 24404 KB Output is correct
9 Correct 15 ms 24532 KB Output is correct
10 Correct 14 ms 24456 KB Output is correct
11 Incorrect 13 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 14 ms 23780 KB Output is correct
2 Correct 14 ms 24248 KB Output is correct
3 Correct 14 ms 24356 KB Output is correct
4 Correct 12 ms 23936 KB Output is correct
5 Correct 15 ms 24356 KB Output is correct
6 Correct 16 ms 25052 KB Output is correct
7 Correct 14 ms 24124 KB Output is correct
8 Correct 14 ms 24404 KB Output is correct
9 Correct 15 ms 24532 KB Output is correct
10 Correct 14 ms 24456 KB Output is correct
11 Correct 614 ms 75088 KB Output is correct
12 Correct 1184 ms 92000 KB Output is correct
13 Execution timed out 4045 ms 105588 KB Time limit exceeded
14 Halted 0 ms 0 KB -