oj.uz

Submission #382336

# Submission time Handle Problem Language Result Execution time Memory
382336 2021-03-27T06:08:06 Z alireza_kaviani Parachute rings (IOI12_rings) C++11
0 / 100
 3226 ms 117336 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define X			first
#define Y			second

const int MAXN = 1e6 + 10;

int n , flag , invalid[5] , cycle[5] , root[5] , sz[5][MAXN] , par[5][MAXN] , deg[5][MAXN];
vector<int> adj[MAXN];
vector<pii> E;

void Init(int N_) {
	n = N_;
	for(int i = 0 ; i < 5 ; i++){
		fill(par[i] , par[i] + MAXN , -1);
		fill(sz[i] , sz[i] + MAXN , -1);
		root[i] = -1;
	}
	root[0] = 0;
}

int Find(int ind , int v){
	return (par[ind][v] == -1 ? v : par[ind][v] = Find(ind , par[ind][v]));
}

void Union(int ind , int v , int u){
	v = Find(ind , v); u = Find(ind , u);
	if(v == u)	return;
	if(sz[ind][v] < sz[ind][u])	swap(v , u);
	par[ind][u] = v;
	sz[ind][v] += sz[ind][u];
}

void add(int ind , int v , int u){
	if(root[ind] == -1)	return;
	if(v == root[ind] || u == root[ind])	return;
	deg[ind][v]++; deg[ind][u]++;
	if(deg[ind][v] >= 3 || deg[ind][u] >= 3)	invalid[ind] = 1;
	if(Find(ind , v) == Find(ind , u)){
		if(cycle[ind] != 0)	cycle[ind] = -1;
		else	cycle[ind] = sz[ind][Find(ind , v)];
	}
	else	Union(ind , v , u);
}

void Link(int A, int B) {
	A++; B++;
	E.push_back({A , B});
	adj[A].push_back(B);
	adj[B].push_back(A);
	for(int i = 0 ; i < 5 ; i++)	add(i , A , B);
	if(flag)	return;
	if(deg[0][A] < deg[0][B])	swap(A , B);
	if(deg[0][A] >= 3){
		flag = 1;
		root[1] = A; root[2] = adj[A][0];
		root[3] = adj[A][1]; root[4] = adj[A][2];
		for(pii i : E){
			for(int j = 1 ; j < 5 ; j++)	add(j , i.X , i.Y);
		}
	}
}

int CountCritical() {
	if(invalid[0] == 0){
		if(cycle[0] == 0)	return n;
		if(cycle[0] > 0)	return cycle[0];
	}
	int ans = 0;
	for(int i = 0 ; i < 5 ; i++){
		if(invalid[i] == 0 && cycle[i] == 0)	ans++;
	}
	return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62956 KB Output is correct
2 Correct 42 ms 63212 KB Output is correct
3 Correct 42 ms 63340 KB Output is correct
4 Incorrect 40 ms 62956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 85332 KB Output is correct
2 Correct 1739 ms 110056 KB Output is correct
3 Correct 3226 ms 117336 KB Output is correct
4 Incorrect 1193 ms 106056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62956 KB Output is correct
2 Correct 42 ms 63212 KB Output is correct
3 Correct 42 ms 63340 KB Output is correct
4 Incorrect 40 ms 62956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62956 KB Output is correct
2 Correct 42 ms 63212 KB Output is correct
3 Correct 42 ms 63340 KB Output is correct
4 Incorrect 40 ms 62956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62956 KB Output is correct
2 Correct 42 ms 63212 KB Output is correct
3 Correct 42 ms 63340 KB Output is correct
4 Incorrect 40 ms 62956 KB Output isn't correct
5 Halted 0 ms 0 KB -