oj.uz

답안 #577191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577191 2022-06-14T08:56:06 Z AngusWong 낙하산 고리들 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -