oj.uz

Submission #350129

# Submission time Handle Problem Language Result Execution time Memory
350129 2021-01-19T02:24:34 Z Kevin_Zhang_TW Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 51492 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 553 ms 24108 KB Output is correct
3 Correct 167 ms 24044 KB Output is correct
4 Correct 48 ms 23916 KB Output is correct
5 Correct 395 ms 24044 KB Output is correct
6 Correct 1111 ms 24156 KB Output is correct
7 Correct 76 ms 23844 KB Output is correct
8 Correct 730 ms 24044 KB Output is correct
9 Correct 63 ms 24152 KB Output is correct
10 Correct 101 ms 24156 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 51492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 553 ms 24108 KB Output is correct
3 Correct 167 ms 24044 KB Output is correct
4 Correct 48 ms 23916 KB Output is correct
5 Correct 395 ms 24044 KB Output is correct
6 Correct 1111 ms 24156 KB Output is correct
7 Correct 76 ms 23844 KB Output is correct
8 Correct 730 ms 24044 KB Output is correct
9 Correct 63 ms 24152 KB Output is correct
10 Correct 101 ms 24156 KB Output is correct
11 Execution timed out 4069 ms 24272 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 553 ms 24108 KB Output is correct
3 Correct 167 ms 24044 KB Output is correct
4 Correct 48 ms 23916 KB Output is correct
5 Correct 395 ms 24044 KB Output is correct
6 Correct 1111 ms 24156 KB Output is correct
7 Correct 76 ms 23844 KB Output is correct
8 Correct 730 ms 24044 KB Output is correct
9 Correct 63 ms 24152 KB Output is correct
10 Correct 101 ms 24156 KB Output is correct
11 Execution timed out 4069 ms 24272 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 553 ms 24108 KB Output is correct
3 Correct 167 ms 24044 KB Output is correct
4 Correct 48 ms 23916 KB Output is correct
5 Correct 395 ms 24044 KB Output is correct
6 Correct 1111 ms 24156 KB Output is correct
7 Correct 76 ms 23844 KB Output is correct
8 Correct 730 ms 24044 KB Output is correct
9 Correct 63 ms 24152 KB Output is correct
10 Correct 101 ms 24156 KB Output is correct
11 Execution timed out 4054 ms 51492 KB Time limit exceeded
12 Halted 0 ms 0 KB -