#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
static const int MAXN = 10013;
static const int MAGIC = 60;
static int N, R;
static vi edge[MAXN];
static int dsu[MAXN];
static vi ord;
static vi nodes[MAXN];
static bool vis[MAXN], inside[MAXN];
static int parent[MAXN], label[MAXN];
static int get(int u)
{
return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
static bool merge(int u, int v)
{
u = get(u);
v = get(v);
if (u == v)
{
return false;
}
dsu[u] = v;
return true;
}
static void gen()
{
//generates all the labels for all the nodes.
queue<int> q; q.push(0);
while(!q.empty())
{
int u = q.front(); q.pop();
label[u] = SZ(nodes[0]);
nodes[0].PB(u);
vis[u] = true;
if (SZ(nodes[0]) == MAGIC)
{
break;
}
for (int v : edge[u])
{
if (vis[v])
{
continue;
}
parent[v] = u;
q.push(v);
}
}
FOR(i, 1, SZ(nodes[0]))
{
nodes[nodes[0][i]] = nodes[0];
}
while(!q.empty())
{
int u = q.front(); q.pop();
vis[u] = true;
for (int v : nodes[parent[u]])
{
inside[v] = true;
//you just wanna find any leaf, except w
}
nodes[u] = nodes[parent[u]];
FOR(i, 0, SZ(nodes[parent[u]]))
{
int v = nodes[parent[u]][i];
if (v == parent[u]) continue;
int c = 0;
for (int x : edge[v])
{
if (inside[x]) c++;
}
if (c == 1)
{
label[u] = label[v];
nodes[parent[u][i]] = u;
break;
}
}
for (int v : nodes[parent[u]])
{
inside[v] = false;
//you just wanna find any leaf, except w
}
for (int v : edge[u])
{
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
void Joi(int n, int m, int e1[], int e2[], ll val, int subtask)
{
N = n;
iota(dsu, dsu + N, 0);
FOR(i, 0, m)
{
int u = e1[i], v = e2[i];
if (merge(u, v))
{
edge[u].PB(v);
edge[v].PB(u);
}
}
gen();
FOR(i, 0, N)
{
int x = label[i];
MessageBoard(i, (val & (1ll << x)) ? 1 : 0);
}
//generate a tree for each node.
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
static const int MAXN = 10013;
static int N, R, V = -1;
static vi edge[MAXN];
static int dsu[MAXN];
static int depth[MAXN], parent[MAXN], pos[MAXN];
static ll ans;
static vi ord;
static ll solved = 0;
static bool vis[MAXN], inside[MAXN];
static int parent[MAXN], label[MAXN];
static int get(int u)
{
return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
static bool merge(int u, int v)
{
u = get(u);
v = get(v);
if (u == v)
{
return false;
}
dsu[u] = v;
return true;
}
static void gen()
{
//generates all the labels for all the nodes.
queue<int> q; q.push(0);
while(!q.empty())
{
int u = q.front(); q.pop();
label[u] = SZ(nodes[0]);
nodes[0].PB(u);
vis[u] = true;
if (SZ(nodes[0]) == MAGIC)
{
break;
}
for (int v : edge[u])
{
if (vis[v])
{
continue;
}
parent[v] = u;
q.push(v);
}
}
FOR(i, 1, SZ(nodes[0]))
{
nodes[nodes[0][i]] = nodes[0];
}
while(!q.empty())
{
int u = q.front(); q.pop();
vis[u] = true;
for (int v : nodes[parent[u]])
{
inside[v] = true;
//you just wanna find any leaf, except w
}
nodes[u] = nodes[parent[u]];
FOR(i, 0, SZ(nodes[parent[u]]))
{
int v = nodes[parent[u]][i];
if (v == parent[u]) continue;
int c = 0;
for (int x : edge[v])
{
if (inside[x]) c++;
}
if (c == 1)
{
label[u] = label[v];
nodes[parent[u][i]] = u;
break;
}
}
for (int v : nodes[parent[u]])
{
inside[v] = false;
//you just wanna find any leaf, except w
}
for (int v : edge[u])
{
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
void dfs(int u, int p, int va)
{
int x = label[u];
if (va)
{
ans += (1ll << x);
}
for (int v : edge[u])
{
if (v == p || !inside[v])
{
continue;
}
dfs(v, u, Move(v));
Move(u);
}
}
ll Ioi(int n, int m, int e1[], int e2[], int st, int va, int subtask)
{
N = n;
iota(dsu, dsu + N, 0);
FOR(i, 0, m)
{
int u = e1[i], v = e2[i];
if (merge(u, v))
{
edge[u].PB(v);
edge[v].PB(u);
// cerr << "edge " << u << ' ' << v << endl;
}
}
gen();
FOR(i, 0, N)
{
inside[i] = false;
}
for (int u : nodes[st])
{
inside[u] = true;
}
dfs(st, N, va);
return ans;
}
Compilation message
Joi.cpp: In function 'void gen()':
Joi.cpp:114:34: error: invalid types 'int[int]' for array subscript
nodes[parent[u][i]] = u;
^
Joi.cpp: At global scope:
Joi.cpp:41:15: warning: 'R' defined but not used [-Wunused-variable]
static int N, R;
^
Ioi.cpp:48:23: error: redefinition of 'int parent [10013]'
static int parent[MAXN], label[MAXN];
^
Ioi.cpp:43:25: note: 'int parent [10013]' previously declared here
static int depth[MAXN], parent[MAXN], pos[MAXN];
^~~~~~
Ioi.cpp: In function 'void gen()':
Ioi.cpp:72:23: error: 'nodes' was not declared in this scope
label[u] = SZ(nodes[0]);
^
Ioi.cpp:24:23: note: in definition of macro 'SZ'
#define SZ(x) ((int) (x).size())
^
Ioi.cpp:75:29: error: 'MAGIC' was not declared in this scope
if (SZ(nodes[0]) == MAGIC)
^~~~~
Ioi.cpp:89:18: error: 'nodes' was not declared in this scope
FOR(i, 1, SZ(nodes[0]))
^
Ioi.cpp:26:46: note: in definition of macro 'FOR'
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
^
Ioi.cpp:89:15: note: in expansion of macro 'SZ'
FOR(i, 1, SZ(nodes[0]))
^~
Ioi.cpp:97:22: error: 'nodes' was not declared in this scope
for (int v : nodes[parent[u]])
^~~~~
Ioi.cpp:102:9: error: 'nodes' was not declared in this scope
nodes[u] = nodes[parent[u]];
^~~~~
Ioi.cpp:115:34: error: invalid types 'int[int]' for array subscript
nodes[parent[u][i]] = u;
^
Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:171:18: error: 'nodes' was not declared in this scope
for (int u : nodes[st])
^~~~~
Ioi.cpp: At global scope:
Ioi.cpp:46:11: warning: 'solved' defined but not used [-Wunused-variable]
static ll solved = 0;
^~~~~~
Ioi.cpp:43:39: warning: 'pos' defined but not used [-Wunused-variable]
static int depth[MAXN], parent[MAXN], pos[MAXN];
^~~
Ioi.cpp:43:12: warning: 'depth' defined but not used [-Wunused-variable]
static int depth[MAXN], parent[MAXN], pos[MAXN];
^~~~~
Ioi.cpp:40:18: warning: 'V' defined but not used [-Wunused-variable]
static int N, R, V = -1;
^
Ioi.cpp:40:15: warning: 'R' defined but not used [-Wunused-variable]
static int N, R, V = -1;
^
