oj.uz

Submission #760662

# Submission time Handle Problem Language Result Execution time Memory
760662 2023-06-18T05:35:13 Z ymm Parachute rings (IOI12_rings) C++17
0 / 100
 821 ms 136552 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r)  for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

//vector<int> inter(vector<int> a, vector<int>
//

const int N = 1<<20;
vector<int> A[N];
int n;

struct graph {
	int deg[N];
	int rem;
	int par[N];
	bool has3;
	int sz[N];
	int szc;

	void init() { memset(par, -1, sizeof(par)); szc = -1; rem = -1; }
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	void unite(int v, int u) {
		if (v == rem || u == rem)
			return;
		deg[v]++;
		deg[u]++;
		if (deg[v] >= 3 || deg[u] >= 3)
			has3 = 1;
		v = rt(v);
		u = rt(u);
		if (v == u) {
			szc = szc == -1? sz[v]: -2;
			return;
		}
		if (sz[v] < sz[u])
			swap(v, u);
		par[u] = v;
		sz[v] += sz[u];
	}
};

void make_by_rem(graph &G, int rem) {
	G.init();
	G.rem = rem;
	Loop (v,0,n) {
		for (int u : A[v]) {
			if (v > u)
				continue;
			G.unite(v, u);
		}
	}
}

graph G, G3[4], G4;

int v3 = -1, v4 = -1;

void Init(int N_) {
	n = N_;
	G.init();
}

void Link(int v, int u) {
	A[v].push_back(u);
	A[u].push_back(v);

	if (v4 != -1) {
		G4.unite(v, u);
	} else if (v3 != -1) {
		for (auto &G : G3)
			G.unite(v, u);
	} else {
		G.unite(v, u);
	}

	for (int x : {v, u}) {
		if (v3 == -1 && A[x].size() == 3) {
			v3 = x;
			make_by_rem(G3[0], x);
			Loop (i,0,3)
				make_by_rem(G3[i+1], A[x][i]);
		}
		if (v4 == -1 && A[x].size() == 4) {
			v4 = x;
			make_by_rem(G4, x);
		}
	}
}

int CountCritical() {
	if (v4 != -1) {
		return G4.szc == -1 && !G4.has3;
	} else if (v3 != -1) {
		int ans = 0;
		for (auto &G : G3)
			ans += G.szc == -1 && !G.has3;
		return ans;
	} else {
		switch (G.szc) {
		case -2: return 0;
		case -1: return n;
		default: return G.szc;
		}
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29000 KB Output is correct
2 Correct 23 ms 50016 KB Output is correct
3 Correct 23 ms 50132 KB Output is correct
4 Incorrect 14 ms 29016 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 56200 KB Output is correct
2 Correct 741 ms 122944 KB Output is correct
3 Correct 821 ms 136552 KB Output is correct
4 Incorrect 800 ms 81548 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29000 KB Output is correct
2 Correct 23 ms 50016 KB Output is correct
3 Correct 23 ms 50132 KB Output is correct
4 Incorrect 14 ms 29016 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29000 KB Output is correct
2 Correct 23 ms 50016 KB Output is correct
3 Correct 23 ms 50132 KB Output is correct
4 Incorrect 14 ms 29016 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29000 KB Output is correct
2 Correct 23 ms 50016 KB Output is correct
3 Correct 23 ms 50132 KB Output is correct
4 Incorrect 14 ms 29016 KB Output isn't correct
5 Halted 0 ms 0 KB -