#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10010, MAXBIT = 60;
vector < int > adj[MAXN];
int used[MAXN], acord[MAXN];
vector < int > ord;
int last_bit;
void dfs(int v, ll X)
{
used[v] = 1;
acord[v] = last_bit;
/**if (last_bit == 59)
{
cout << "info " << (X & ((ll)(1) << last_bit)) << " " << ((X & ((ll)(1) << last_bit)) > 0) << endl;
}*/
///cout << "Vertex " << v << " " << last_bit << endl;
MessageBoard(v, ((X & ((ll)(1) << last_bit)) > 0));
last_bit ++;
if (last_bit == MAXBIT)
last_bit = 0;
ord.push_back(v);
for (int u : adj[v])
{
if (used[u])
continue;
dfs(u, X);
ord.push_back(v);
}
}
void build_tree(int N, int M, int A[], int B[], ll X)
{
for (int i = M - 1; i < M; i ++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(32, X);
ord.pop_back();
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
build_tree(N, M, A, B, X);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10010, MAXBIT = 60;
vector < int > graph[MAXN];
int marked[MAXN], linked[MAXN];
vector < int > path;
int next_bit;
void dfs(int v)
{
marked[v] = 1;
linked[v] = next_bit ++;
if (next_bit == MAXBIT)
next_bit = 0;
//MessageBoard(v, ((X & ((ll)(1) << bit)) > 0));
path.push_back(v);
for (int u : graph[v])
{
if (marked[u])
continue;
dfs(u);
path.push_back(v);
}
}
void build_tree(int N, int M, int A[], int B[])
{
for (int i = 0; i < M; i ++)
{
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
}
dfs(32);
path.pop_back();
}
int bit_val[MAXBIT], ch[MAXBIT];
int min_step[MAXN], from[MAXN];
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
build_tree(N, M, A, B);
int pos = 0;
while(path[pos] != P)
pos ++;
vector < int > tk = path;
for (int cur : tk)
path.push_back(cur);
/**for (int cur : path)
cout << cur << " ";
cout << endl;*/
bit_val[linked[P]] = V;
ch[linked[P]] = 1;
int ver = P;
for (int i = 0; i < N; i ++)
{
min_step[i] = 4 * N;
from[i] = -1;
}
for (int s = 0; s < tk.size(); s ++)
{
ll ds = 0;
int pivot = s;
while(pivot < path.size())
{
//cout << s << " : " << pivot << " " << ds << " " << endl;
ds |= ((ll)(1) << linked[path[pivot]]);
if (ds == ((ll)(1) << MAXBIT) - 1)
break;
pivot ++;
}
assert(pivot < path.size());
if (pivot - s < min_step[path[s]])
{
from[path[s]] = s;
min_step[path[s]] = pivot - s;
}
}
ll ds = 0;
bool done = false;
int best_to = -1, best_val = 300;
for (int to = 0; to < 120; to ++)
{
if (to + min_step[path[pos + to]] <= best_val)
{
best_val = to + min_step[path[pos + to]];
best_to = to;
}
}
assert(best_to != - 1);
int to = best_to;
for (int d = 1; d <= to; d ++)
{
bit_val[linked[path[pos + d]]] = Move(path[pos + d]);
ch[linked[path[pos + d]]] = 1;
///cout << "add " << linked[path[pos + d]];
}
ver = path[pos + to];
for (int d = 1; d <= min_step[ver]; d ++)
{
bit_val[linked[path[from[ver] + d]]] = Move(path[from[ver] + d]);
ch[linked[path[from[ver] + d]]] = 1;
///cout << "add " << linked[path[from[ver] + d]] << endl;
}
done = true;
/*
for (int step = 0; ds != ((ll)(1) << MAXBIT) - 1; step ++)
{
int nxt = (pos + 1) % (int)(path.size());
//cout << "move from " << ver << " " << path[nxt] << endl;
ver = path[nxt];
int res = Move(ver);
///assert(step != 119);
//cout << "linked " << linked[ver] << " " << res << endl;
bit_val[linked[ver]] = res;
ch[linked[ver]] = 1;
ds |= ((ll)(1) << linked[ver]);
pos = nxt;
}*/
ll X = 0;
for (int bit = 0; bit < MAXBIT; bit ++)
{
//if (ch[bit] == 0)
//cout << "FUCK " << bit << endl;
assert(ch[bit]);
if (bit_val[bit] > 0)
X |= ((ll)(1) << bit);
}
//cout << "X " << X << endl;
return X;
}
Compilation message
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int s = 0; s < tk.size(); s ++)
| ~~^~~~~~~~~~~
Ioi.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | while(pivot < path.size())
| ~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Ioi.cpp:3:
Ioi.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | assert(pivot < path.size());
| ~~~~~~^~~~~~~~~~~~~
Ioi.cpp:94:6: warning: unused variable 'ds' [-Wunused-variable]
94 | ll ds = 0;
| ^~
Ioi.cpp:95:8: warning: variable 'done' set but not used [-Wunused-but-set-variable]
95 | bool done = false;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1308 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1548 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1308 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1564 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1564 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
