답안 #760823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760823 2023-06-18T15:30:31 Z Sohsoh84 낙하산 고리들 (IOI12_rings) C++17
17 / 100
1546 ms 109772 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;
		deg[ind][i] = 0;
	}

	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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23724 KB Output is correct
2 Correct 12 ms 24264 KB Output is correct
3 Correct 13 ms 24404 KB Output is correct
4 Correct 11 ms 23772 KB Output is correct
5 Correct 13 ms 23900 KB Output is correct
6 Incorrect 15 ms 24148 KB Output isn't correct
7 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 50220 KB Output is correct
2 Correct 918 ms 92632 KB Output is correct
3 Correct 1546 ms 105416 KB Output is correct
4 Correct 824 ms 74504 KB Output is correct
5 Correct 817 ms 74568 KB Output is correct
6 Correct 837 ms 73292 KB Output is correct
7 Correct 1415 ms 104572 KB Output is correct
8 Correct 1039 ms 104356 KB Output is correct
9 Correct 1085 ms 109772 KB Output is correct
10 Correct 549 ms 73072 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23724 KB Output is correct
2 Correct 12 ms 24264 KB Output is correct
3 Correct 13 ms 24404 KB Output is correct
4 Correct 11 ms 23772 KB Output is correct
5 Correct 13 ms 23900 KB Output is correct
6 Incorrect 15 ms 24148 KB Output isn't correct
7 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23724 KB Output is correct
2 Correct 12 ms 24264 KB Output is correct
3 Correct 13 ms 24404 KB Output is correct
4 Correct 11 ms 23772 KB Output is correct
5 Correct 13 ms 23900 KB Output is correct
6 Incorrect 15 ms 24148 KB Output isn't correct
7 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23724 KB Output is correct
2 Correct 12 ms 24264 KB Output is correct
3 Correct 13 ms 24404 KB Output is correct
4 Correct 11 ms 23772 KB Output is correct
5 Correct 13 ms 23900 KB Output is correct
6 Incorrect 15 ms 24148 KB Output isn't correct
7 Halted 0 ms 0 KB -