oj.uz

Submission #761132

# Submission time Handle Problem Language Result Execution time Memory
761132 2023-06-19T08:52:05 Z SanguineChameleon Parachute rings (IOI12_rings) C++17
0 / 100
 262 ms 47444 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 20;
vector<pair<int, int>> edges;
int deg[4][maxn];
int L[4][maxn];
int R[4][maxn];
int cand[4];
bool good[4];
int n;

void Init(int _n) {
	n = _n;
	for (int k = 0; k < 4; k++) {
		cand[k] = -1;
	}
}

void update(int k, int u, int v) {
	if (!good[k]) {
		return;
	}
	if (u == cand[k] || v == cand[k]) {
		return;
	}
	if (deg[k][u] == 2 || deg[k][v] == 2) {
		good[k] = false;
		return;
	}
	deg[k][u]++;
	deg[k][v]++;
	int lu = L[k][u];
	int ru = R[k][u];
	int lv = L[k][v];
	int rv = R[k][v];
	assert(u == lu || u == ru);
	assert(v == lv || v == rv);
	if (lu == lv) {
		good[k] = false;
		return;
	}
	if (lu == u) {
		swap(lu, ru);
		L[k][lu] = lu;
		L[k][ru] = lu;
		R[k][lu] = ru;
		R[k][ru] = ru;
	}
	if (rv == v) {
		swap(lv, rv);
		L[k][lv] = lv;
		L[k][rv] = lv;
		R[k][lv] = rv;
		R[k][rv] = rv;
	}
	L[k][lu] = lu;
	R[k][lu] = rv;
	L[k][rv] = lu;
	R[k][rv] = rv;
}

void Link(int u, int v) {
	if (cand[0] == -1) {
		edges.emplace_back(u, v);
		deg[0][u]++;
		deg[0][v]++;
		if (deg[0][v] == 3) {
			swap(u, v);
		}
		if (deg[0][u] == 3) {
			cand[0] = u;
			int cnt = 0;
			for (auto e: edges) {
				if (e.first == u) {
					cand[++cnt] = e.second;
				}
				else if (e.second == u) {
					cand[++cnt] = e.first;
				}
			}
			for (int k = 0; k < 4; k++) {
				good[k] = true;
				for (int i = 0; i < n; i++) {
					deg[k][i] = 0;
					L[k][i] = i;
					R[k][i] = i;
				}
			}
			for (auto e: edges) {
				for (int k = 0; k < 4; k++) {
					update(k, e.first, e.second);
				}
			}
			edges.clear();
		}
	}
	else {
		for (int k = 0; k < 4; k++) {
			update(k, u, v);
		}
	}
}

int CountCritical() {
	if (cand[0] == -1) {
		return n;
	}
	else {
		return good[0] + good[1] + good[2] + good[3];
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 6568 KB Output is correct
2 Correct 262 ms 40124 KB Output is correct
3 Correct 153 ms 47444 KB Output is correct
4 Incorrect 160 ms 12516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -