#include "Joi.h"
#include <bits/stdc++.h>
typedef long long ll;
const int Nmax = 30005;
using namespace std;
static int tmp;
static bool used[Nmax];
static int In[Nmax], w[Nmax], level[Nmax], down[Nmax], t[Nmax];
static vector<int> v[Nmax];
static void dfs1(int node = 0)
{
used[node] = 1;
down[node] = 1;
w[node] = 1;
for(auto it : v[node])
if(!used[it])
{
t[it] = node;
level[it] = level[node] + 1;
dfs1(it);
w[node] += w[it];
down[node] = max(down[node], down[it] + 1);
}
}
static void change_edges(int N)
{
int i;
for(i=0; i<N; ++i)
{
vector<int> good;
for(auto it : v[i])
if(t[it] == i)
good.push_back(it);
int j, act = 0;
for(j=0; j<good.size(); ++j)
if(down[good[j]] > down[good[act]]) act = j;
if(!good.empty()) swap(good[act], good[0]);
v[i] = good;
}
}
static void dfs2(int node = 0)
{
In[node] = ++tmp;
for(auto it : v[node]) dfs2(it);
}
void Joi(int N, int M, int A[], int B[], ll X, int _T)
{
int i;
for(i=0; i<M; ++i)
{
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
dfs1();
change_edges(N);
if(down[0] >= 60) /// coloreaza pe inaltimi si gata
{
for(i=0; i<N; ++i)
MessageBoard(i, (X >> (level[i] % 60)) &1);
return;
}
dfs2();
for(i=0; i<N; ++i)
MessageBoard(i, ((X >> (In[i] % 60)) &1));
}
#include "Ioi.h"
#include <bits/stdc++.h>
typedef long long ll;
const int Nmax = 30005;
const ll AllBits = (1LL << 60) - 1;
using namespace std;
static int tmp;
static bool used[Nmax];
static int ord[Nmax], In[Nmax], w[Nmax], level[Nmax], down[Nmax], t[Nmax], take[Nmax];
static vector<int> v[Nmax];
static bool Down = 0;
static void dfs1(int node = 0)
{
used[node] = 1;
down[node] = 1;
w[node] = 1;
for(auto it : v[node])
if(!used[it])
{
t[it] = node;
level[it] = level[node] + 1;
dfs1(it);
w[node] += w[it];
down[node] = max(down[node], down[it] + 1);
}
}
static void change_edges(int N)
{
int i;
for(i=0; i<N; ++i)
{
vector<int> good;
for(auto it : v[i])
if(t[it] == i)
good.push_back(it);
int j, act = 0;
for(j=0; j<good.size(); ++j)
if(down[good[j]] > down[good[act]]) act = j;
if(!good.empty()) swap(good[act], good[0]);
v[i] = good;
}
}
static void dfs2(int node = 0)
{
In[node] = ++tmp; ord[tmp] = node;
for(auto it : v[node]) dfs2(it);
}
static ll solve1(int node, ll Mask, ll Ans)
{
if(Mask == AllBits) return Ans;
if(node == 0) Down = 1;
if(Down)
{
ll w = (1LL << level[v[node][0] % 60]);
ll res = Move(v[node][0]) * w;
return solve1(v[node][0], Mask | w, Ans | res);
}
else
{
ll w = (1LL << level[t[node] % 60]);
ll res = Move(t[node]) * w;
return solve1(t[node], Mask | w, Ans | res);
}
}
static void solve2(int node, ll &Mask, ll &Ans, int &cnt)
{
if(Mask == AllBits) return;
if(In[node] > down[0])
{
--cnt;
for(auto it : v[node])
if(cnt > 0)
{
int res = Move(it);
Mask |= (1LL << (In[it] % 60));
if(res) Ans |= (1LL << (In[it] % 60));
solve2(it, Mask, Ans, cnt);
Move(node);
}
return;
}
int i;
for(i=1; i<v[node].size() && take[node]; ++i)
{
int x = v[node][i], pos = min(w[x], take[node]);
int res = Move(x);
Mask |= (1LL << (In[x] % 60));
if(res) Ans |= (1LL << (In[x] % 60));
solve2(x, Mask, Ans, pos);
Move(node);
take[node] -= pos;
}
int x = v[node][0];
int res = Move(x);
Mask |= (1LL << (In[x] % 60));
if(res) Ans |= (1LL << (In[x] % 60));
solve2(x, Mask, Ans, cnt);
}
ll Ioi(int N, int M, int A[], int B[], int P, int V, int _T)
{
int i;
for(i=0; i<M; ++i)
{
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
dfs1();
change_edges(N);
if(down[0] >= 60) /// coloreaza pe inaltimi si gata
return solve1(P, (1LL << (level[P] % 60)), V * (1LL << (level[P] % 60)));
dfs2();
int rest = 60 - down[0];
for(i=down[0] - 1; i; --i)
{
int node, sub;
node = ord[i];
sub = w[node] - w[ord[i+1]] - 1;
take[node] = min(sub, rest);
rest -= take[node];
}
ll Mask, Ans;
Mask = (1LL << (In[P] % 60));
Ans = V * Mask;
while(P)
{
P = t[P];
int res = Move(P);
Mask |= (1LL << (In[P] % 60));
if(res) Ans |= (1LL << (In[P] % 60));
}
int cnt = -1;
solve2(0, Mask, Ans, cnt);
return Ans;
}
Compilation message
Joi.cpp: In function 'void change_edges(int)':
Joi.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<good.size(); ++j)
~^~~~~~~~~~~~
Ioi.cpp: In function 'void change_edges(int)':
Ioi.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<good.size(); ++j)
~^~~~~~~~~~~~
Ioi.cpp: In function 'void solve2(int, ll&, ll&, int&)':
Ioi.cpp:95:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=1; i<v[node].size() && take[node]; ++i)
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2416 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2192 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2164 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
2160 KB |
Wrong Answer [8] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5476 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2160 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2160 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2160 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2708 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2700 KB |
Output is correct |
| 6 |
Correct |
6 ms |
2580 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2708 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2572 KB |
Output is correct |
| 9 |
Correct |
15 ms |
4860 KB |
Output is correct |
| 10 |
Correct |
15 ms |
5020 KB |
Output is correct |
| 11 |
Correct |
15 ms |
4872 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2176 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2196 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2160 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
5604 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
5616 KB |
Wrong Answer [8] |
| 2 |
Halted |
0 ms |
0 KB |
- |
