# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
288608 |
2020-09-01T16:47:31 Z |
emil_physmath |
Game (IOI14_game) |
C++17 |
|
747 ms |
54392 KB |
#include <unordered_set>
#include <list>
#include <random>
#include <chrono>
#include <iostream>
#include <algorithm>
#include <vector>
#include "game.h"
using namespace std;
const int maxN = 1500;
#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
struct custom_hash {
int operator()(int x) const {
static const int FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return (x + FIXED_RANDOM);
}
};
struct Set
{
list<int>::iterator itOf[maxN];
bool is[maxN];
list<int> a;
Set()
{
for (int x = 0; x < maxN; ++x)
is[x] = false;
}
void insert(int x)
{
if (!is[x])
{
a.push_back(x);
itOf[x] = prev(a.end());
is[x] = true;
}
}
void erase(int x)
{
if (!is[x])
{
a.erase(itOf[x]);
is[x] = false;
}
}
int size() { return a.size(); }
void clear() { a.clear(); }
list<int>::iterator begin() { return a.begin(); }
list<int>::iterator end() { return a.end(); }
};
int n;
Set jmp[maxN];
int nei[maxN][maxN];
int par[maxN], sz[maxN], centre[maxN];
int Root(int v) {
return v == par[v] ? v : par[v] = Root(par[v]);
}
void Union(int u, int v)
{
u = Root(u); v = Root(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
if (rnd(0, 69) <= 5) swap(u, v);
int c1 = centre[u], c2 = centre[v];
if (jmp[c1].size() > jmp[c2].size()) swap(c1, c2);
for (int t: jmp[c1])
{
if (t == c2) continue;
nei[t][c1] = 0;
jmp[t].erase(c1);
nei[c2][t] += nei[c1][t];
nei[t][c2] += nei[c1][t];
jmp[t].insert(c2);
jmp[c2].insert(t);
}
jmp[c1].clear();
sz[v] += sz[u];
par[u] = v;
centre[v] = c2;
}
void initialize(int n_) {
n = n_;
for (int v = 0; v < n; ++v)
par[v] = v, sz[v] = 1, centre[v] = v;
}
int hasEdge(int u, int v) {
int c1 = centre[Root(u)];
int c2 = centre[Root(v)];
jmp[c1].insert(c2);
jmp[c2].insert(c1);
++nei[c1][c2];
++nei[c2][c1];
if (nei[c1][c2] == sz[Root(u)] * sz[Root(v)])
{
Union(u, v);
return 1;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
20224 KB |
Output is correct |
2 |
Correct |
12 ms |
20352 KB |
Output is correct |
3 |
Correct |
12 ms |
20224 KB |
Output is correct |
4 |
Correct |
15 ms |
20224 KB |
Output is correct |
5 |
Correct |
11 ms |
20224 KB |
Output is correct |
6 |
Correct |
11 ms |
20224 KB |
Output is correct |
7 |
Correct |
12 ms |
20224 KB |
Output is correct |
8 |
Correct |
11 ms |
20256 KB |
Output is correct |
9 |
Correct |
12 ms |
20224 KB |
Output is correct |
10 |
Correct |
11 ms |
20224 KB |
Output is correct |
11 |
Correct |
12 ms |
20224 KB |
Output is correct |
12 |
Correct |
11 ms |
20224 KB |
Output is correct |
13 |
Correct |
13 ms |
20224 KB |
Output is correct |
14 |
Correct |
13 ms |
20224 KB |
Output is correct |
15 |
Correct |
12 ms |
20224 KB |
Output is correct |
16 |
Correct |
12 ms |
20224 KB |
Output is correct |
17 |
Correct |
13 ms |
20224 KB |
Output is correct |
18 |
Correct |
13 ms |
20224 KB |
Output is correct |
19 |
Correct |
12 ms |
20224 KB |
Output is correct |
20 |
Correct |
12 ms |
20224 KB |
Output is correct |
21 |
Correct |
12 ms |
20224 KB |
Output is correct |
22 |
Correct |
13 ms |
20224 KB |
Output is correct |
23 |
Correct |
12 ms |
20216 KB |
Output is correct |
24 |
Correct |
13 ms |
20224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
20200 KB |
Output is correct |
2 |
Correct |
12 ms |
20224 KB |
Output is correct |
3 |
Correct |
15 ms |
20224 KB |
Output is correct |
4 |
Correct |
12 ms |
20224 KB |
Output is correct |
5 |
Correct |
16 ms |
20224 KB |
Output is correct |
6 |
Correct |
11 ms |
20224 KB |
Output is correct |
7 |
Correct |
12 ms |
20224 KB |
Output is correct |
8 |
Correct |
12 ms |
20200 KB |
Output is correct |
9 |
Correct |
11 ms |
20224 KB |
Output is correct |
10 |
Correct |
11 ms |
20224 KB |
Output is correct |
11 |
Correct |
11 ms |
20224 KB |
Output is correct |
12 |
Correct |
13 ms |
20224 KB |
Output is correct |
13 |
Correct |
12 ms |
20224 KB |
Output is correct |
14 |
Correct |
13 ms |
20224 KB |
Output is correct |
15 |
Correct |
12 ms |
20224 KB |
Output is correct |
16 |
Correct |
13 ms |
20224 KB |
Output is correct |
17 |
Correct |
12 ms |
20224 KB |
Output is correct |
18 |
Correct |
13 ms |
20224 KB |
Output is correct |
19 |
Correct |
12 ms |
20224 KB |
Output is correct |
20 |
Correct |
12 ms |
20224 KB |
Output is correct |
21 |
Correct |
12 ms |
20224 KB |
Output is correct |
22 |
Correct |
12 ms |
20224 KB |
Output is correct |
23 |
Correct |
13 ms |
20224 KB |
Output is correct |
24 |
Correct |
12 ms |
20224 KB |
Output is correct |
25 |
Correct |
13 ms |
20352 KB |
Output is correct |
26 |
Correct |
12 ms |
20352 KB |
Output is correct |
27 |
Correct |
12 ms |
20352 KB |
Output is correct |
28 |
Correct |
12 ms |
20352 KB |
Output is correct |
29 |
Correct |
13 ms |
20352 KB |
Output is correct |
30 |
Correct |
12 ms |
20352 KB |
Output is correct |
31 |
Correct |
13 ms |
20352 KB |
Output is correct |
32 |
Correct |
12 ms |
20352 KB |
Output is correct |
33 |
Correct |
13 ms |
20352 KB |
Output is correct |
34 |
Correct |
14 ms |
20608 KB |
Output is correct |
35 |
Correct |
14 ms |
20608 KB |
Output is correct |
36 |
Correct |
14 ms |
20608 KB |
Output is correct |
37 |
Correct |
14 ms |
20608 KB |
Output is correct |
38 |
Correct |
14 ms |
20608 KB |
Output is correct |
39 |
Correct |
14 ms |
20608 KB |
Output is correct |
40 |
Correct |
14 ms |
20608 KB |
Output is correct |
41 |
Correct |
13 ms |
20608 KB |
Output is correct |
42 |
Correct |
14 ms |
20608 KB |
Output is correct |
43 |
Correct |
14 ms |
20480 KB |
Output is correct |
44 |
Correct |
14 ms |
20480 KB |
Output is correct |
45 |
Correct |
14 ms |
20608 KB |
Output is correct |
46 |
Correct |
14 ms |
20608 KB |
Output is correct |
47 |
Correct |
15 ms |
20608 KB |
Output is correct |
48 |
Correct |
14 ms |
20608 KB |
Output is correct |
49 |
Correct |
14 ms |
20608 KB |
Output is correct |
50 |
Correct |
13 ms |
20608 KB |
Output is correct |
51 |
Correct |
17 ms |
20608 KB |
Output is correct |
52 |
Correct |
13 ms |
20608 KB |
Output is correct |
53 |
Correct |
13 ms |
20608 KB |
Output is correct |
54 |
Correct |
13 ms |
20608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
20224 KB |
Output is correct |
2 |
Correct |
12 ms |
20224 KB |
Output is correct |
3 |
Correct |
12 ms |
20224 KB |
Output is correct |
4 |
Correct |
12 ms |
20224 KB |
Output is correct |
5 |
Correct |
12 ms |
20224 KB |
Output is correct |
6 |
Correct |
12 ms |
20224 KB |
Output is correct |
7 |
Correct |
12 ms |
20224 KB |
Output is correct |
8 |
Correct |
14 ms |
20224 KB |
Output is correct |
9 |
Correct |
13 ms |
20224 KB |
Output is correct |
10 |
Correct |
12 ms |
20224 KB |
Output is correct |
11 |
Correct |
13 ms |
20224 KB |
Output is correct |
12 |
Correct |
12 ms |
20224 KB |
Output is correct |
13 |
Correct |
13 ms |
20256 KB |
Output is correct |
14 |
Correct |
12 ms |
20224 KB |
Output is correct |
15 |
Correct |
12 ms |
20224 KB |
Output is correct |
16 |
Correct |
13 ms |
20224 KB |
Output is correct |
17 |
Correct |
12 ms |
20224 KB |
Output is correct |
18 |
Correct |
12 ms |
20224 KB |
Output is correct |
19 |
Correct |
12 ms |
20224 KB |
Output is correct |
20 |
Correct |
12 ms |
20224 KB |
Output is correct |
21 |
Correct |
13 ms |
20224 KB |
Output is correct |
22 |
Correct |
12 ms |
20224 KB |
Output is correct |
23 |
Correct |
12 ms |
20224 KB |
Output is correct |
24 |
Correct |
12 ms |
20224 KB |
Output is correct |
25 |
Correct |
13 ms |
20352 KB |
Output is correct |
26 |
Correct |
13 ms |
20352 KB |
Output is correct |
27 |
Correct |
13 ms |
20352 KB |
Output is correct |
28 |
Correct |
12 ms |
20352 KB |
Output is correct |
29 |
Correct |
12 ms |
20352 KB |
Output is correct |
30 |
Correct |
13 ms |
20352 KB |
Output is correct |
31 |
Correct |
12 ms |
20352 KB |
Output is correct |
32 |
Correct |
13 ms |
20352 KB |
Output is correct |
33 |
Correct |
12 ms |
20352 KB |
Output is correct |
34 |
Correct |
14 ms |
20608 KB |
Output is correct |
35 |
Correct |
14 ms |
20608 KB |
Output is correct |
36 |
Correct |
14 ms |
20608 KB |
Output is correct |
37 |
Correct |
14 ms |
20608 KB |
Output is correct |
38 |
Correct |
14 ms |
20736 KB |
Output is correct |
39 |
Correct |
14 ms |
20608 KB |
Output is correct |
40 |
Correct |
14 ms |
20608 KB |
Output is correct |
41 |
Correct |
14 ms |
20608 KB |
Output is correct |
42 |
Correct |
13 ms |
20608 KB |
Output is correct |
43 |
Correct |
13 ms |
20480 KB |
Output is correct |
44 |
Correct |
14 ms |
20480 KB |
Output is correct |
45 |
Correct |
14 ms |
20608 KB |
Output is correct |
46 |
Correct |
13 ms |
20608 KB |
Output is correct |
47 |
Correct |
14 ms |
20608 KB |
Output is correct |
48 |
Correct |
14 ms |
20608 KB |
Output is correct |
49 |
Correct |
14 ms |
20608 KB |
Output is correct |
50 |
Correct |
15 ms |
20608 KB |
Output is correct |
51 |
Correct |
14 ms |
20608 KB |
Output is correct |
52 |
Correct |
14 ms |
20608 KB |
Output is correct |
53 |
Correct |
14 ms |
20608 KB |
Output is correct |
54 |
Correct |
14 ms |
20608 KB |
Output is correct |
55 |
Correct |
76 ms |
25080 KB |
Output is correct |
56 |
Correct |
79 ms |
25080 KB |
Output is correct |
57 |
Correct |
78 ms |
25052 KB |
Output is correct |
58 |
Correct |
83 ms |
25084 KB |
Output is correct |
59 |
Correct |
78 ms |
25080 KB |
Output is correct |
60 |
Correct |
82 ms |
25080 KB |
Output is correct |
61 |
Correct |
77 ms |
25208 KB |
Output is correct |
62 |
Correct |
77 ms |
25080 KB |
Output is correct |
63 |
Correct |
86 ms |
25080 KB |
Output is correct |
64 |
Correct |
63 ms |
23032 KB |
Output is correct |
65 |
Correct |
62 ms |
23032 KB |
Output is correct |
66 |
Correct |
81 ms |
26104 KB |
Output is correct |
67 |
Correct |
84 ms |
25976 KB |
Output is correct |
68 |
Correct |
81 ms |
26104 KB |
Output is correct |
69 |
Correct |
81 ms |
25976 KB |
Output is correct |
70 |
Correct |
81 ms |
26104 KB |
Output is correct |
71 |
Correct |
67 ms |
24184 KB |
Output is correct |
72 |
Correct |
67 ms |
24312 KB |
Output is correct |
73 |
Correct |
70 ms |
24184 KB |
Output is correct |
74 |
Correct |
69 ms |
24312 KB |
Output is correct |
75 |
Correct |
68 ms |
24312 KB |
Output is correct |
76 |
Correct |
171 ms |
29176 KB |
Output is correct |
77 |
Correct |
177 ms |
29340 KB |
Output is correct |
78 |
Correct |
177 ms |
29176 KB |
Output is correct |
79 |
Correct |
177 ms |
29304 KB |
Output is correct |
80 |
Correct |
181 ms |
29144 KB |
Output is correct |
81 |
Correct |
174 ms |
29176 KB |
Output is correct |
82 |
Correct |
172 ms |
29176 KB |
Output is correct |
83 |
Correct |
173 ms |
29256 KB |
Output is correct |
84 |
Correct |
175 ms |
29176 KB |
Output is correct |
85 |
Correct |
315 ms |
33900 KB |
Output is correct |
86 |
Correct |
310 ms |
33784 KB |
Output is correct |
87 |
Correct |
327 ms |
33784 KB |
Output is correct |
88 |
Correct |
305 ms |
33656 KB |
Output is correct |
89 |
Correct |
306 ms |
33628 KB |
Output is correct |
90 |
Correct |
309 ms |
33784 KB |
Output is correct |
91 |
Correct |
315 ms |
33964 KB |
Output is correct |
92 |
Correct |
309 ms |
33656 KB |
Output is correct |
93 |
Correct |
325 ms |
33784 KB |
Output is correct |
94 |
Correct |
747 ms |
44792 KB |
Output is correct |
95 |
Correct |
724 ms |
54392 KB |
Output is correct |
96 |
Correct |
730 ms |
54392 KB |
Output is correct |
97 |
Correct |
719 ms |
54140 KB |
Output is correct |
98 |
Correct |
725 ms |
54184 KB |
Output is correct |
99 |
Correct |
715 ms |
54136 KB |
Output is correct |
100 |
Correct |
711 ms |
54136 KB |
Output is correct |