oj.uz

답안 #382389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382389 2021-03-27T08:20:06 Z alishahali1382 낙하산 고리들 (IOI12_rings) C++14
0 / 100
 1587 ms 63124 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=1000010, LOG=20;

int n, m, k, u, v, x, y, t, a, b;
int tree=1, deg3, ans0, cycle;
int A[MAXN], B[MAXN], deg[MAXN];
vector<int> G[MAXN], V;

struct DSU{
	int par[MAXN];
	DSU(){
		iota(par, par+MAXN, 0);
	}
	int get(int x){ return (par[x]==x?x:par[x]=get(par[x]));}
	int join(int x, int y){
		x=get(x);
		y=get(y);
		par[x]=y;
		return x!=y;
	}
} dsu;
struct Solver{
	int deg[MAXN], root, ok=1;
	DSU dsu;
	void add_edge(int u, int v){
		if (u==root || v==root) return ;
		ok&=dsu.join(u, v);
		ok&=(2>=++deg[u]);
		ok&=(2>=++deg[v]);
	}
	int Get(){ return ok;}
} solver[4];


void Init(int nn){
	n=nn;
}
void Link(int u, int v){
	if (ans0) return ;
	if (deg3){
		for (int i:{0, 1, 2, 3}) solver[i].add_edge(u, v);
		return ;
	}
	A[m]=u;
	B[m]=v;
	m++;
	deg[u]++;
	deg[v]++;
	if (deg[u]==3) swap(u, v);
	if (deg[v]==3){
		V={v};
		for (int i=0; i<m; i++) if (A[i]==v || B[i]==v) V.pb(v^A[i]^B[i]);
		for (int i:{0, 1, 2, 3}){
			solver[i].root=V[i];
			for (int j=0; j<m; j++) solver[i].add_edge(A[j], B[j]);
		}
		deg3=1;
		return ;
	}
	if (dsu.join(u, v)) return ;
	if (tree) tree=0;
	else ans0=1;
}
int CountCritical(){
	if (ans0) return 0;
	if (deg3){
		int res=0;
		for (int i:{0, 1, 2, 3}) res+=solver[i].Get();
		return res;
	}
	if (tree) return n;
	int res=0;
	for (int i=0; i<n; i++) if (dsu.get(i)==dsu.get(cycle)) res++;
	return res;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 43372 KB Output is correct
2 Correct 31 ms 43500 KB Output is correct
3 Correct 31 ms 43628 KB Output is correct
4 Incorrect 30 ms 43500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 49600 KB Output is correct
2 Correct 794 ms 61292 KB Output is correct
3 Correct 1587 ms 63124 KB Output is correct
4 Incorrect 471 ms 55148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 43372 KB Output is correct
2 Correct 31 ms 43500 KB Output is correct
3 Correct 31 ms 43628 KB Output is correct
4 Incorrect 30 ms 43500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 43372 KB Output is correct
2 Correct 31 ms 43500 KB Output is correct
3 Correct 31 ms 43628 KB Output is correct
4 Incorrect 30 ms 43500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 43372 KB Output is correct
2 Correct 31 ms 43500 KB Output is correct
3 Correct 31 ms 43628 KB Output is correct
4 Incorrect 30 ms 43500 KB Output isn't correct
5 Halted 0 ms 0 KB -