#include <stdio.h>
#include "Joi.h"
#include <vector>
#include <set>
#define SZ 60
static std::vector<int> AdjList[10005];
static std::set<int> Set[10005];
static int Vis[10005];
static int Role[10005];
// static int HELLO = 0;
static void FirstSet(int u, int pa)
{
// printf("FirstSet u%d pa%d s%d\n", u, pa, AdjList[u].size());
if (Set[0].size() < SZ)
{
Role[u] = Set[0].size();
Set[0].insert(u);
}
int i, j, v;
Vis[u] = 1;
for (i = 0; i < AdjList[u].size(); i++)
{
v = AdjList[u][i];
// printf(".");
if (v != pa)
{
// printf(".");
if (!Vis[v])
{
// HELLO++;
FirstSet(v, u);
// HELLO--;
}
else
{
AdjList[u].erase(AdjList[u].begin() + i);
for (j = 0; j < AdjList[v].size(); j++)
if (AdjList[v][j] == u)
break;
if (j < AdjList[v].size())
AdjList[v].erase(AdjList[v].begin() + j);
else
printf("WTF\n");
i--;
}
}
}
}
// static int HELLO;
static void OtherSet(int u, int pa)
{
// printf("OtherSet u%d pa%d\n", u, pa);
// HELLO++;
int i, j, v, s, d;
if (u != 0)
{
Set[u] = Set[pa];
if (Set[u].find(u) == Set[u].end())
{
std::set<int>::iterator it;
Set[u].insert(u);
// for (it = Set[u].begin(); it != Set[u].end(); it++)
// printf("%d ", *it);
// printf("\n");
for (it = Set[u].begin(); it != Set[u].end(); it++)
{
if (*it == pa || *it == u)
continue;
s = AdjList[*it].size();
d = 0;
for (j = 0; j < s; j++)
{
if (Set[u].find(AdjList[*it][j]) != Set[u].end())
{
// printf("%d-%d\n", *it, AdjList[*it][j]);
d++;
}
// else
// printf("%d-%dX\n", *it, AdjList[*it][j]);
}
if (d == 1)
break;
}
if (it != Set[u].end())
{
Role[u] = Role[*it];
Set[u].erase(it);
// printf("u %d pa %d erase %d d %d\n", u, pa, *it, d);
}
}
}
s = AdjList[u].size();
for (i = 0; i < s; i++)
{
v = AdjList[u][i];
if (v != pa && Set[v].size() == 0)
{
OtherSet(v, u);
}
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
int i;
for (i = 0; i < M; i++)
{
AdjList[A[i]].push_back(B[i]);
AdjList[B[i]].push_back(A[i]);
}
FirstSet(0, -1);
// printf("FirstSet fin\n");
// for (i = 0; i < N; i++)
// HELLO += AdjList[i].size();
// printf("HELLO %d\n", HELLO);
OtherSet(0, -1);
// printf("OtherSet fin %d\n", HELLO);
int val[SZ];
for (i = 0; i < SZ; i++)
{
val[i] = X%2;
X >>= 1;
}
for (i = 0; i < N; i++)
{
MessageBoard(i, val[Role[i]]);
}
// printf("Joi fin\n");
}
#include <stdio.h>
#include "Ioi.h"
#include <vector>
#include <set>
#define SZ 60
static std::vector<int> AdjList[10005];
static std::set<int> Set[10005];
static int Vis[10005];
static int Role[10005];
static void FirstSet(int u, int pa)
{
// printf("FirstSet u%d pa%d s%d\n", u, pa, AdjList[u].size());
if (Set[0].size() < SZ)
{
Role[u] = Set[0].size();
Set[0].insert(u);
}
int i, j, v;
Vis[u] = 1;
for (i = 0; i < AdjList[u].size(); i++)
{
v = AdjList[u][i];
// printf(".");
if (v != pa)
{
// printf(".");
if (!Vis[v])
{
// HELLO++;
FirstSet(v, u);
// HELLO--;
}
else
{
AdjList[u].erase(AdjList[u].begin() + i);
for (j = 0; j < AdjList[v].size(); j++)
if (AdjList[v][j] == u)
break;
if (j < AdjList[v].size())
AdjList[v].erase(AdjList[v].begin() + j);
else
printf("WTF\n");
i--;
}
}
}
}
// static int HELLO;
static void OtherSet(int u, int pa)
{
// printf("OtherSet u%d\n", u);
// HELLO++;
int i, j, v, s, d;
if (u != 0)
{
Set[u] = Set[pa];
if (Set[u].find(u) == Set[u].end())
{
std::set<int>::iterator it;
Set[u].insert(u);
for (it = Set[u].begin(); it != Set[u].end(); it++)
{
if (*it == pa || *it == u)
continue;
s = AdjList[*it].size();
d = 0;
for (j = 0; j < s; j++)
{
if (Set[u].find(AdjList[*it][j]) != Set[u].end())
d++;
}
if (d == 1)
break;
}
if (it != Set[u].end())
{
Role[u] = Role[*it];
Set[u].erase(it);
}
}
}
s = AdjList[u].size();
for (i = 0; i < s; i++)
{
v = AdjList[u][i];
if (v != pa && Set[v].size() == 0)
{
OtherSet(v, u);
}
}
}
static int val[SZ];
// static int HELLO;
void GetVal(int P, int u, int pa)
{
// printf("GetVal %d %d\n", u, pa);
// HELLO++;
int i, v, s = AdjList[u].size();
Vis[u] = 1;
for (i = 0; i < s; i++)
{
v = AdjList[u][i];
if (v != pa && !Vis[v] && Set[P].find(v) != Set[P].end())
{
val[Role[v]] = Move(v);
GetVal(P, v, u);
Move(u);
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
int i;
for (i = 0; i < M; i++)
{
AdjList[A[i]].push_back(B[i]);
AdjList[B[i]].push_back(A[i]);
}
FirstSet(0, -1);
OtherSet(0, -1);
val[Role[P]] = V;
for (i = 0; i < N; i++)
Vis[i] = 0;
std::set<int>::iterator it;
// for (i = 0; i < N; i++)
// printf("%d\n", Set[i].size());
GetVal(P, P, -1);
// printf("GetVal fin %d %d\n", Set[P].size(), HELLO);
long long X = 0;
for (i = SZ - 1; i >= 0; i--)
{
X <<= 1;
X += val[i];
}
// printf("X %lld\n", X);
return X;
}
