oj.uz

Submission #256794

# Submission time Handle Problem Language Result Execution time Memory
256794 2020-08-03T08:16:10 Z SpeedOfMagic Game (IOI14_game) C++17
15 / 100
 2 ms 384 KB 
#include "game.h"

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> cnt;  // cnt[i][j] = how many edges are forbidden between i and j
vector<int> repr, siz;

int ffind(int a) { return (a == repr[a]) ? a : repr[a] = ffind(repr[a]); }

void unite(int u, int v) {  // O(N), O(N^2) amortized
	u = ffind(u); v = ffind(v);
	if (u == v) return;
	if (siz[u] > siz[v]) swap(u, v);
	repr[u] = v; siz[v] += siz[u];
	for (size_t i = 0; i < cnt.size(); ++i)
		cnt[v][i] += cnt[u][i];
}

void initialize(int n) {
	cnt.resize(n, vector<int>(n, 0));
	repr.resize(n);
	for (int i = 0; i < n; ++i)
		repr[i] = i;
	siz.resize(n, 1);
}

int hasEdge(int u, int v) {
	int ru = ffind(u), rv = ffind(v);
	if (cnt[ru][rv] + 1 == siz[ru] * siz[rv]) {  // We must unite!
		unite(ru, rv);
		return 1;
	} else {  // Nah, we can wait
		++cnt[ru][rv];
		++cnt[rv][ru];
		return 0;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 0 ms 256 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 0 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 0 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 0 ms 256 KB Output is correct
24 Correct 0 ms 256 KB Output is correct
25 Incorrect 1 ms 384 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 376 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 0 ms 256 KB Output is correct
23 Correct 0 ms 256 KB Output is correct
24 Correct 0 ms 256 KB Output is correct
25 Incorrect 1 ms 384 KB Output isn't correct
26 Halted 0 ms 0 KB -