| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1155974 | an22inkle | Game (IOI14_game) | C++17 | Compilation error | 0 ms | 0 KiB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using paira = array<int, 2>;
using ll = long long;
/*
We need to know-
Each vertices' components - To do this in O(1), we need to implement DSU
The count of "no" edges between components
When will we be merging? Exactly when there are |c_u| * |c_j| - 1 "no" edges between two components
*/
int N = 2;
vector<vector<int>> edges(N, vector<int>(N)); // # of NO edges between components
// dsu stuff
vector<int> parent(N);
vector<int> size(N, 0);
void new_compo(int x) {
parent[x] = x;
size[x] = 1;
}
int get_compo(int x) {
if (parent[x] == x) return x;
return parent[x] = get_compo(parent[x]);
}
void union_compo(int x, int y) {
x = get_compo(x);
y = get_compo(y);
if (x != y) {
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
}
}
void initialize(int n) {
N = n;
edges.resize(N, vector<int>(N));
parent.resize(N);
size.resize(N);
for (int i = 0; i < N; i++) {
new_compo(i);
}
}
int hasEdge(int u, int v) {
if (u > v) swap(u, v);
int cu = get_compo(u);
int cv = get_compo(v);
// cout << size[cu] << ' ' << size[cv] << '\n';
if (size[cu] < size[cv]) swap(cu, cv);
if (edges[cu][cv] == 1LL*size[cu]*size[cv] - 1) {
// We must answer YES now
// cv chotota
// chototar parent hobe borota
// chotota deleted
// cv deleted
union_compo(cu, cv);
for (int i = 0; i < N; i++) {
if (i == cu) continue;
edges[cu][i] += edges[cv][i];
return 1;
}
}
edges[cu][cv]++;
return 0;
}
Compilation message (stderr)
game.cpp: In function 'void new_compo(int)':
game.cpp:27:5: error: reference to 'size' is ambiguous
27 | size[x] = 1;
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp: In function 'void union_compo(int, int)':
game.cpp:41:13: error: reference to 'size' is ambiguous
41 | if (size[x] < size[y]) swap(x, y);
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp:41:23: error: reference to 'size' is ambiguous
41 | if (size[x] < size[y]) swap(x, y);
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp:43:9: error: reference to 'size' is ambiguous
43 | size[x] += size[y];
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp:43:20: error: reference to 'size' is ambiguous
43 | size[x] += size[y];
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp: In function 'void initialize(int)':
game.cpp:51:5: error: reference to 'size' is ambiguous
51 | size.resize(N);
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:65:9: error: reference to 'size' is ambiguous
65 | if (size[cu] < size[cv]) swap(cu, cv);
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp:65:20: error: reference to 'size' is ambiguous
65 | if (size[cu] < size[cv]) swap(cu, cv);
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp:66:30: error: reference to 'size' is ambiguous
66 | if (edges[cu][cv] == 1LL*size[cu]*size[cv] - 1) {
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~
game.cpp:66:39: error: reference to 'size' is ambiguous
66 | if (edges[cu][cv] == 1LL*size[cu]*size[cv] - 1) {
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from game.cpp:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
254 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
245 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
game.cpp:23:13: note: 'std::vector<int> size'
23 | vector<int> size(N, 0);
| ^~~~