#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct UnionFind {
vector<int> p, ranks;
UnionFind(int n) : p(n), ranks(n, 0) {
for(int i = 0; i < n; ++i) {
p[i] = i;
}
}
int find_set(int a) {
return p[a] == a ? a : p[a] = find_set(p[a]);
}
bool is_same_set(int a, int b) {
return find_set(a) == find_set(b);
}
void unite(int a, int b) {
int x = find_set(a), y = find_set(b);
if(x != y) {
if(ranks[x] > ranks[y])
p[y] = x;
else {
p[x] = y;
if(ranks[x] == ranks[y]) {
++ranks[y];
}
}
}
}
};
static vector<vector<int>> adj;
static int tim = 0;
static vector<int> ts;
static vector<int> path;
static void dfs(int u) {
ts[u] = tim++;
path.push_back(u);
for(int v : adj[u]) {
if(ts[v] == -1) {
dfs(v);
path.push_back(u);
}
}
}
static void find_tree(int n, int m, signed A[], signed B[]) {
adj.resize(n);
UnionFind uf(n);
vector<pair<int, int>> edges(m);
for(int i = 0; i < m; ++i) {
edges[i] = {min(A[i], B[i]), max(A[i], B[i])};
}
sort(edges.begin(), edges.end());
int k = 0;
for(pair<int, int> p : edges) {
int u = p.first, v = p.second;
if(!uf.is_same_set(u, v)) {
uf.unite(u, v);
adj[u].push_back(v);
adj[v].push_back(u);
++k;
}
}
assert(k == n-1);
ts.assign(n, -1);
dfs(0);
/*cout << "ts: { ";
for(int i = 0; i < n; ++i) {
cout << ts[i] << ", ";
}
cout << "}\n";
cout << "path: { ";
for(int i : path) {
cout << i << ", ";
}
cout << "}" << endl;*/
}
void Joi(signed n, signed m, signed A[], signed B[], long long X, signed T) {
int seq[60];
//cout << "seq: { ";
for(int i = 0; i < 60; ++i) {
seq[i] = ((X&(1LL << i)) > 0);
//cout << seq[i] << ", ";
}
//cout << "}" << endl;
find_tree(n, m, A, B);
for(int i = 0; i < n; ++i) {
assert(ts[i] != -1);
MessageBoard(i, seq[ts[i]%60]);
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct UnionFind {
vector<int> p, ranks;
UnionFind(int n) : p(n), ranks(n, 0) {
for(int i = 0; i < n; ++i) {
p[i] = i;
}
}
int find_set(int a) {
return p[a] == a ? a : p[a] = find_set(p[a]);
}
bool is_same_set(int a, int b) {
return find_set(a) == find_set(b);
}
void unite(int a, int b) {
int x = find_set(a), y = find_set(b);
if(x != y) {
if(ranks[x] > ranks[y])
p[y] = x;
else {
p[x] = y;
if(ranks[x] == ranks[y]) {
++ranks[y];
}
}
}
}
};
static vector<vector<int>> adj;
static int tim = 0;
static vector<int> ts;
static vector<int> path;
static void dfs(int u) {
ts[u] = tim++;
path.push_back(u);
for(int v : adj[u]) {
if(ts[v] == -1) {
dfs(v);
path.push_back(u);
}
}
}
static void find_tree(int n, int m, signed A[], signed B[]) {
adj.resize(n);
UnionFind uf(n);
vector<pair<int, int>> edges(m);
for(int i = 0; i < m; ++i) {
edges[i] = {min(A[i], B[i]), max(A[i], B[i])};
}
sort(edges.begin(), edges.end());
for(pair<int, int> p : edges) {
int u = p.first, v = p.second;
if(!uf.is_same_set(u, v)) {
uf.unite(u, v);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
ts.assign(n, -1);
dfs(0);
}
long long Ioi(signed n, signed m, signed A[], signed B[], signed p, signed v, signed T) {
find_tree(n, m, A, B);
int seq[60];
seq[ts[p]%60] = v;
int i;
for(i = 0; i < path.size(); ++i) {
if(path[i] == p) {
break;
}
}
if(path[i] != p) while(true);
if(path.front() != path.back()) while(true);
for(int k = 0; k < 120; ++k) {
int prev = i;
i = (i+1)%path.size();
if(i == path.size()-1) {
i = 0;
}
if(find(adj[path[prev]].begin(), adj[path[prev]].end()) == adj[path[prev]].end()) while(true);
int res = Move(path[i]);
seq[ts[path[i]]%60] = res;
}
int X = 0;
for(int j = 0; j < 60; ++j)
X |= seq[j] << j;
return X;
}
Compilation message
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < path.size(); ++i) {
~~^~~~~~~~~~~~~
Ioi.cpp:92:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == path.size()-1) {
~~^~~~~~~~~~~~~~~~
Ioi.cpp:95:59: error: no matching function for call to 'find(std::vector<long long int>::iterator, std::vector<long long int>::iterator)'
if(find(adj[path[prev]].begin(), adj[path[prev]].end()) == adj[path[prev]].end()) while(true);
^
In file included from /usr/include/c++/7/bits/locale_facets.h:48:0,
from /usr/include/c++/7/bits/basic_ios.h:37,
from /usr/include/c++/7/ios:44,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from Ioi.cpp:3:
/usr/include/c++/7/bits/streambuf_iterator.h:369:5: note: candidate: template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)
find(istreambuf_iterator<_CharT> __first,
^~~~
/usr/include/c++/7/bits/streambuf_iterator.h:369:5: note: template argument deduction/substitution failed:
Ioi.cpp:95:59: note: '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >' is not derived from 'std::istreambuf_iterator<_CharT>'
if(find(adj[path[prev]].begin(), adj[path[prev]].end()) == adj[path[prev]].end()) while(true);
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from Ioi.cpp:3:
/usr/include/c++/7/bits/stl_algo.h:3899:5: note: candidate: template<class _IIter, class _Tp> _IIter std::find(_IIter, _IIter, const _Tp&)
find(_InputIterator __first, _InputIterator __last,
^~~~
/usr/include/c++/7/bits/stl_algo.h:3899:5: note: template argument deduction/substitution failed:
Ioi.cpp:95:59: note: candidate expects 3 arguments, 2 provided
if(find(adj[path[prev]].begin(), adj[path[prev]].end()) == adj[path[prev]].end()) while(true);
^
