oj.uz

Submission #578873

# Submission time Handle Problem Language Result Execution time Memory
578873 2022-06-18T07:00:18 Z AngusWong Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 101704 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N=1e6+1;
int n, viss, 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_, viss=0;
	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 st, int ed, int prev=-1){
	vis[x]=viss, par[x]=prev;
    if (x==ed){
        int t=x;
		while (t!=st){
			cyc.push_back(t);
			t=par[t];
			assert(t!=-1);
		}
        cyc.push_back(st);
		setcrit(cyc);
        return;
    }
	for (int i: v[x]){
		if (vis[i]!=viss){
			dfs(i, st, ed, x);
			continue;
		}
	}
	vis[x]=2;
}
 
void Link(int A, int B) {
	cnt[A]=min(cnt[A]+1, 4), cnt[B]=min(cnt[B]+1, 4);
	if (find(A)!=find(B)) join(A, B);
	else{
        viss++;
        cyc.clear();
		dfs(A, A, B);
	}
	v[A].push_back(B);
	v[B].push_back(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 13 ms 23840 KB Output is correct
2 Correct 19 ms 24304 KB Output is correct
3 Correct 15 ms 24232 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 24424 KB Output is correct
6 Correct 20 ms 25044 KB Output is correct
7 Correct 13 ms 24188 KB Output is correct
8 Correct 15 ms 24368 KB Output is correct
9 Correct 15 ms 24228 KB Output is correct
10 Correct 16 ms 24404 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 81600 KB Output is correct
2 Correct 1016 ms 101704 KB Output is correct
3 Execution timed out 4093 ms 97472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23840 KB Output is correct
2 Correct 19 ms 24304 KB Output is correct
3 Correct 15 ms 24232 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 24424 KB Output is correct
6 Correct 20 ms 25044 KB Output is correct
7 Correct 13 ms 24188 KB Output is correct
8 Correct 15 ms 24368 KB Output is correct
9 Correct 15 ms 24228 KB Output is correct
10 Correct 16 ms 24404 KB Output is correct
11 Incorrect 53 ms 24396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23840 KB Output is correct
2 Correct 19 ms 24304 KB Output is correct
3 Correct 15 ms 24232 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 24424 KB Output is correct
6 Correct 20 ms 25044 KB Output is correct
7 Correct 13 ms 24188 KB Output is correct
8 Correct 15 ms 24368 KB Output is correct
9 Correct 15 ms 24228 KB Output is correct
10 Correct 16 ms 24404 KB Output is correct
11 Incorrect 53 ms 24396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23840 KB Output is correct
2 Correct 19 ms 24304 KB Output is correct
3 Correct 15 ms 24232 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 15 ms 24424 KB Output is correct
6 Correct 20 ms 25044 KB Output is correct
7 Correct 13 ms 24188 KB Output is correct
8 Correct 15 ms 24368 KB Output is correct
9 Correct 15 ms 24228 KB Output is correct
10 Correct 16 ms 24404 KB Output is correct
11 Correct 499 ms 81600 KB Output is correct
12 Correct 1016 ms 101704 KB Output is correct
13 Execution timed out 4093 ms 97472 KB Time limit exceeded
14 Halted 0 ms 0 KB -