Submission #350129

#	Time	Username	Problem	Language	Result	Execution time	Memory
350129		Kevin_Zhang_TW	Parachute rings (IOI12_rings)	C++17	20 / 100	4069 ms	51492 KiB

rings

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 1000005;

int N, res;

struct dsu {
	vector<int> g, sz;
	dsu (int n) { g.resize(n+1), sz.resize(n+1, 1), iota(AI(g), 0); }
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	bool M(int a, int b) { 
		a = F(a), b = F(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a, b);
		return sz[a] += sz[b], g[b] = a, true;
	}
};

vector<int> edge[MAX_N];

int deg[MAX_N], cntdeg[MAX_N];

void Init(int N_) {

	N = N_;
	res = N;
	cntdeg[0] = N;

}
bool check(int id) {
	dsu D(N);
	int cpp = N - 1, degsum = 0;
	for (int i = 0;i < N;++i) if (i != id) {
		int cnt = 0;
		for (int u : edge[i]) if (u != id) {
			if (D.M(u, i)) --cpp;
			++cnt;
			++degsum;
		}
		if (cnt > 2) return false;
	}
	return degsum / 2 - (N - 1) + cpp == 0;
}

void Link(int A, int B) {
	DE(A, B);
	edge[A].pb(B), edge[B].pb(A);
}

int CountCritical() {
	int res = 0;
	for (int i = 0;i < N;++i)
		if (check(i)) ++res;
	return res;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
rings.cpp:61:2: note: in expansion of macro 'DE'
   61 |  DE(A, B);
      |  ^~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31