oj.uz

Submission #760820

# Submission time Handle Problem Language Result Execution time Memory
760820 2023-06-18T15:10:06 Z Sohsoh84 Parachute rings (IOI12_rings) C++17
0 / 100
 942 ms 92608 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define X		first
#define Y		second
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 1e6 + 10;
const ll MAXC = 5;

int n, mx[MAXC], par[MAXC][MAXN], ig[MAXN], deg[MAXC][MAXN], sz[MAXC][MAXN], 
    cyc_cnt[MAXC], cyc_sz[MAXC], cmp = 1;
bool deg_ex;
vector<int> poss, adj[MAXN];
vector<pll> edges;

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

inline void unite(int ind, int u, int v) {
	if (u == ig[ind] || v == ig[ind]) return;

	deg[ind][u]++;
	deg[ind][v]++;
	mx[ind] = max(mx[ind], deg[ind][u]);
	mx[ind] = max(mx[ind], deg[ind][v]);

	u = find(ind, u), v = find(ind, v);
	if (u == v) {
		cyc_cnt[ind]++;
		cyc_sz[ind] += sz[ind][u];
		return;
	}

	par[ind][v] = u;
	sz[ind][u] += sz[ind][v];
}

inline void init(int ind, int v = 0) {
	ig[ind] = v;
	for (int i = 1; i <= n; i++) {
		par[ind][i] = i;
		sz[ind][i] = 1;
	}

	mx[ind] = 0;
	cyc_cnt[ind] = 0;
	cyc_sz[ind] = 0;
	for (auto [u, v] : edges)
		unite(ind, u, v);
}

void Init(int N_) {
	n = N_;
	deg_ex = false;
	init(0);
}

inline void check(int v) {
	if (deg_ex) return;
	if (int(adj[v].size()) > 2) {
		deg_ex = true;
		poss.push_back(v);
		for (int u : adj[v]) poss.push_back(u);

		cmp = poss.size();
		for (int i = 0; i < cmp; i++)
			init(i, poss[i]);
	}
}

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

	check(u);
	check(v);

	for (int i = 0; i < cmp; i++)
		unite(i, u, v);

	edges.push_back({u, v});
}

int CountCritical() {
	if (!deg_ex) {
		if (cyc_cnt[0] == 0) return n;
		else if (cyc_cnt[0] == 1) return cyc_sz[0];
		return 0;
	}

	int ans = 0;
	for (int i = 0; i < cmp; i++)
		if (mx[i] <= 2 && cyc_cnt[i] == 0)
			ans++;

	return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 24276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 50224 KB Output is correct
2 Incorrect 942 ms 92608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 24276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 24276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 24276 KB Output isn't correct
3 Halted 0 ms 0 KB -