| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159928 |
2019-10-25T12:37:50 Z |
rama_pang |
Game (IOI14_game) |
C++14 |
|
460 ms |
16160 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
/* The ideal strategy is to keep saying no unless it is the last
edge such that if we say no, then the graph becomes disconnected.
Assume that the graph is partially filled, such that there are two
components now. How to check if the guessed edge is the last edge?
The number of possible edges between the two components are
sizeA * sizeB. If cur_edge == sizeA * sizeB, then we can add an edge.
Observe that the optimal strategy for the asker is to ask questions
on two disjoint vertices. All already connected vertices are meaningless.
By denying edges, we ensure that the asker would need all Q = N * (N - 1) / 2
questions.
Proof: assume that there are n disjoint components. Let A, B, C, D be sets
with sizeA <= sizeB <= sizeC <= sizeD. What is the optimal strategy of
minimum questions needed? There are a few cases:
1. sizeA * sizeB + sizeC * sizeD + (sizeA + sizeB) * (sizeC + sizeD) total questions.
= sizeA * sizeB + sizeA * sizeC + sizeA * sizeD + sizeB * sizeC + sizeB * sizeD
+ sizeC * sizeD
2. sizeA * sizeB + (sizeA + sizeB) * sizeC + (sizeA + sizeB + sizeC) * sizeD
= sizeA * sizeB + sizeA * sizeC + sizeA * sizeD + sizeB * sizeC + sizeB * sizeD
+ sizeC * sizeD
for any permutation of A, B, C, and D. Thus we can see that for any strategy, if we
give the asker an edge at the last possible edge between two currently disjoint
components, then asker would require the same number of questions.
The total questions needed is: 1 * 1 + 2 * 1 + 3 * 1 + ... = N * (N - 1) / 2.
So the strategy of waiting until last edge of two currently disjoint components is an
optimal strategy.
We can keep track of components' size with disjoint set data structure and countEdges
with adjacency matrix.
*/
struct Disj {
vector<int> p, sz;
void init(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
int par(int n) {
return p[n] == n ? n : p[n] = par(p[n]);
}
bool join(int a, int b) {
a = par(a), b = par(b);
if (a == b) return false;
p[a] = b;
sz[b] += sz[a];
sz[a] = 0;
return true;
}
};
int N;
vector<vector<int>> cnt;
Disj dsu;
void initialize(int n) {
N = n;
cnt.assign(n, vector<int>(n, 0));
dsu.init(n);
}
int hasEdge(int u, int v) {
u = dsu.par(u), v = dsu.par(v);
if (u > v) swap(u, v);
if (++cnt[u][v] == dsu.sz[u] * dsu.sz[v]) {
dsu.join(u, v);
for (int i = 0; i < N; i++) cnt[min(v, i)][max(v, i)] += cnt[min(u, i)][max(u, i)];
return 1;
} else {
return 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
256 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
3 ms |
380 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
424 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
256 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
268 KB |
Output is correct |
| 23 |
Correct |
2 ms |
376 KB |
Output is correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
268 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
380 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
380 KB |
Output is correct |
| 17 |
Correct |
2 ms |
252 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
256 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
2 ms |
256 KB |
Output is correct |
| 24 |
Correct |
2 ms |
380 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| 27 |
Correct |
2 ms |
376 KB |
Output is correct |
| 28 |
Correct |
2 ms |
376 KB |
Output is correct |
| 29 |
Correct |
2 ms |
376 KB |
Output is correct |
| 30 |
Correct |
2 ms |
376 KB |
Output is correct |
| 31 |
Correct |
2 ms |
376 KB |
Output is correct |
| 32 |
Correct |
2 ms |
256 KB |
Output is correct |
| 33 |
Correct |
2 ms |
376 KB |
Output is correct |
| 34 |
Correct |
3 ms |
424 KB |
Output is correct |
| 35 |
Correct |
3 ms |
376 KB |
Output is correct |
| 36 |
Correct |
3 ms |
376 KB |
Output is correct |
| 37 |
Correct |
3 ms |
376 KB |
Output is correct |
| 38 |
Correct |
3 ms |
376 KB |
Output is correct |
| 39 |
Correct |
3 ms |
376 KB |
Output is correct |
| 40 |
Correct |
3 ms |
376 KB |
Output is correct |
| 41 |
Correct |
3 ms |
376 KB |
Output is correct |
| 42 |
Correct |
3 ms |
380 KB |
Output is correct |
| 43 |
Correct |
3 ms |
376 KB |
Output is correct |
| 44 |
Correct |
3 ms |
376 KB |
Output is correct |
| 45 |
Correct |
3 ms |
376 KB |
Output is correct |
| 46 |
Correct |
3 ms |
376 KB |
Output is correct |
| 47 |
Correct |
3 ms |
376 KB |
Output is correct |
| 48 |
Correct |
3 ms |
376 KB |
Output is correct |
| 49 |
Correct |
3 ms |
376 KB |
Output is correct |
| 50 |
Correct |
7 ms |
376 KB |
Output is correct |
| 51 |
Correct |
3 ms |
376 KB |
Output is correct |
| 52 |
Correct |
3 ms |
376 KB |
Output is correct |
| 53 |
Correct |
3 ms |
376 KB |
Output is correct |
| 54 |
Correct |
3 ms |
380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
352 KB |
Output is correct |
| 19 |
Correct |
2 ms |
256 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
252 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
2 ms |
376 KB |
Output is correct |
| 24 |
Correct |
2 ms |
256 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| 27 |
Correct |
2 ms |
376 KB |
Output is correct |
| 28 |
Correct |
2 ms |
376 KB |
Output is correct |
| 29 |
Correct |
2 ms |
376 KB |
Output is correct |
| 30 |
Correct |
2 ms |
256 KB |
Output is correct |
| 31 |
Correct |
2 ms |
256 KB |
Output is correct |
| 32 |
Correct |
2 ms |
376 KB |
Output is correct |
| 33 |
Correct |
2 ms |
348 KB |
Output is correct |
| 34 |
Correct |
4 ms |
376 KB |
Output is correct |
| 35 |
Correct |
3 ms |
376 KB |
Output is correct |
| 36 |
Correct |
3 ms |
376 KB |
Output is correct |
| 37 |
Correct |
3 ms |
376 KB |
Output is correct |
| 38 |
Correct |
3 ms |
376 KB |
Output is correct |
| 39 |
Correct |
3 ms |
376 KB |
Output is correct |
| 40 |
Correct |
3 ms |
376 KB |
Output is correct |
| 41 |
Correct |
3 ms |
376 KB |
Output is correct |
| 42 |
Correct |
3 ms |
380 KB |
Output is correct |
| 43 |
Correct |
3 ms |
376 KB |
Output is correct |
| 44 |
Correct |
3 ms |
376 KB |
Output is correct |
| 45 |
Correct |
3 ms |
376 KB |
Output is correct |
| 46 |
Correct |
3 ms |
376 KB |
Output is correct |
| 47 |
Correct |
3 ms |
376 KB |
Output is correct |
| 48 |
Correct |
3 ms |
376 KB |
Output is correct |
| 49 |
Correct |
3 ms |
376 KB |
Output is correct |
| 50 |
Correct |
4 ms |
376 KB |
Output is correct |
| 51 |
Correct |
3 ms |
376 KB |
Output is correct |
| 52 |
Correct |
3 ms |
376 KB |
Output is correct |
| 53 |
Correct |
3 ms |
376 KB |
Output is correct |
| 54 |
Correct |
3 ms |
376 KB |
Output is correct |
| 55 |
Correct |
58 ms |
2168 KB |
Output is correct |
| 56 |
Correct |
49 ms |
2144 KB |
Output is correct |
| 57 |
Correct |
48 ms |
2168 KB |
Output is correct |
| 58 |
Correct |
48 ms |
2204 KB |
Output is correct |
| 59 |
Correct |
48 ms |
2120 KB |
Output is correct |
| 60 |
Correct |
48 ms |
2168 KB |
Output is correct |
| 61 |
Correct |
48 ms |
2168 KB |
Output is correct |
| 62 |
Correct |
48 ms |
2168 KB |
Output is correct |
| 63 |
Correct |
47 ms |
2168 KB |
Output is correct |
| 64 |
Correct |
44 ms |
2296 KB |
Output is correct |
| 65 |
Correct |
45 ms |
2168 KB |
Output is correct |
| 66 |
Correct |
49 ms |
2168 KB |
Output is correct |
| 67 |
Correct |
48 ms |
2168 KB |
Output is correct |
| 68 |
Correct |
51 ms |
2168 KB |
Output is correct |
| 69 |
Correct |
49 ms |
2168 KB |
Output is correct |
| 70 |
Correct |
48 ms |
2296 KB |
Output is correct |
| 71 |
Correct |
49 ms |
2168 KB |
Output is correct |
| 72 |
Correct |
50 ms |
2156 KB |
Output is correct |
| 73 |
Correct |
48 ms |
2168 KB |
Output is correct |
| 74 |
Correct |
50 ms |
2296 KB |
Output is correct |
| 75 |
Correct |
47 ms |
2168 KB |
Output is correct |
| 76 |
Correct |
112 ms |
4472 KB |
Output is correct |
| 77 |
Correct |
110 ms |
4472 KB |
Output is correct |
| 78 |
Correct |
121 ms |
4488 KB |
Output is correct |
| 79 |
Correct |
108 ms |
4600 KB |
Output is correct |
| 80 |
Correct |
114 ms |
4600 KB |
Output is correct |
| 81 |
Correct |
110 ms |
4564 KB |
Output is correct |
| 82 |
Correct |
113 ms |
4600 KB |
Output is correct |
| 83 |
Correct |
146 ms |
4600 KB |
Output is correct |
| 84 |
Correct |
112 ms |
4652 KB |
Output is correct |
| 85 |
Correct |
330 ms |
7644 KB |
Output is correct |
| 86 |
Correct |
193 ms |
7544 KB |
Output is correct |
| 87 |
Correct |
195 ms |
7672 KB |
Output is correct |
| 88 |
Correct |
201 ms |
7672 KB |
Output is correct |
| 89 |
Correct |
190 ms |
7544 KB |
Output is correct |
| 90 |
Correct |
194 ms |
7672 KB |
Output is correct |
| 91 |
Correct |
195 ms |
7588 KB |
Output is correct |
| 92 |
Correct |
192 ms |
7544 KB |
Output is correct |
| 93 |
Correct |
193 ms |
7544 KB |
Output is correct |
| 94 |
Correct |
440 ms |
16104 KB |
Output is correct |
| 95 |
Correct |
448 ms |
15864 KB |
Output is correct |
| 96 |
Correct |
460 ms |
16160 KB |
Output is correct |
| 97 |
Correct |
447 ms |
15836 KB |
Output is correct |
| 98 |
Correct |
458 ms |
15900 KB |
Output is correct |
| 99 |
Correct |
450 ms |
15912 KB |
Output is correct |
| 100 |
Correct |
448 ms |
16004 KB |
Output is correct |
