oj.uz

Submission #270174

# Submission time Handle Problem Language Result Execution time Memory
270174 2020-08-17T12:58:23 Z Saboon Parachute rings (IOI12_rings) C++14
0 / 100
 266 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int N;
int par[maxn][6], deg[maxn][6];
int e1[maxn], e2[maxn], m = 0;
bool three = false;
int a[6], good[6];
vector<int> g[maxn];
int cntcyc = -1;

int get_par(int v, int c){
	return par[v][c] < 0 ? v : par[v][c] = get_par(par[v][c],c);
}

void merge(int v, int u, int c){
	if (!good[c])
		return;
	int vp = get_par(v,c), up = get_par(u,c);
	if (vp == up){
		good[c] = 0;
		return;
	}
	if (deg[v][c] > 1 or deg[u][c] > 1){
		good[c] = 0;
		return;
	}
	deg[v][c] ++, deg[u][c] ++;
	par[vp][c] = up;
}

void Init(int N_){
	N = N_;
	memset(par, -1, sizeof par);
	for (int i = 1; i <= 4; i++)
		good[i] = 1;
}

void Link(int v, int u){
	if (g[v].size() < g[u].size())
		swap(v,u);
	g[v].push_back(u), g[u].push_back(v);
	if (g[v].size() == 3 and three == false){
		three = true;
		a[1] = v;
		for (int j = 0; j < 3; j++)
			a[j+2] = g[v][j];
		for (int j = 1; j <= 4; j++){
			for (int i = 0; i < m; i++){
				int v = e1[i], u = e2[i];
				if (v != a[j] and u != a[j])
					merge(v,u,j);
			}
		}
	}
	e1[m] = v, e2[m] = u, m++;
	if (three){
		for (int j = 1; j <= 4; j++){
			int v = e1[m-1], u = e2[m-1];
			if (v != a[j] and u != a[j])
				merge(v,u,j);
		}
		return;
	}
	if (get_par(v,0) == get_par(u,0)){
		if (cntcyc == -1)
			cntcyc = -par[get_par(v,0)][0];
		else
			cntcyc = 0;
	}
	else{
		par[u][0] += par[v][0];
		par[v][0] = u;
	}
}

int CountCritical(){
	if (three == 0){
		if (cntcyc == -1)
			return N;
		return cntcyc;
	}
	int ret = 0;
	for (int i = 1; i <= 4; i++)
		if (good[i])
			ret ++;
	return ret;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47352 KB Output is correct
2 Correct 31 ms 47608 KB Output is correct
3 Correct 34 ms 47616 KB Output is correct
4 Incorrect 30 ms 47360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47352 KB Output is correct
2 Correct 31 ms 47608 KB Output is correct
3 Correct 34 ms 47616 KB Output is correct
4 Incorrect 30 ms 47360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47352 KB Output is correct
2 Correct 31 ms 47608 KB Output is correct
3 Correct 34 ms 47616 KB Output is correct
4 Incorrect 30 ms 47360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47352 KB Output is correct
2 Correct 31 ms 47608 KB Output is correct
3 Correct 34 ms 47616 KB Output is correct
4 Incorrect 30 ms 47360 KB Output isn't correct
5 Halted 0 ms 0 KB -