#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10011;
const int MAXL = 60;
static vector<int> grafo[MAXN],tree[MAXN],lista;
static bitset<MAXN> adjMat[MAXN];
static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],relevante[MAXN];
static void bfs(){
memset(contador,0,sizeof(contador));
pai[0] = -1;
contador[0] = 1;
queue<int> fila;
fila.push(0);
while(!fila.empty()){
int v = fila.front();
fila.pop();
lista.push_back(v);
for(int u : grafo[v]){
if(contador[u]) continue;
contador[u] = 1;
pai[u] = v;
fila.push(u);
adjMat[v][u] = 1;
adjMat[u][v] = 1;
}
}
memset(contador,0,sizeof(contador));
}
static void build_first(){
vector<int> primeiro;
for(int i = 0;i<MAXL;i++){
primeiro.push_back(lista[i]);
idx[primeiro.back()] = i;
}
for(int i : primeiro) tree[i] = primeiro;
}
static void extend_tree(int v){
vector<int> copia = tree[pai[v]];
for(int u : copia) relevante[u] = 1;
for(int u : copia){
int w = pai[u];
if(w == -1 || !relevante[w]) continue;
contador[u]++;
contador[w]++;
}
int achei = -1;
for(int u : copia){
if(u == pai[v]) continue;
if(contador[u] == 1){
achei = u;
break;
}
}
for(int u : copia){
contador[u] = 0;
relevante[u] = 0;
if(u != achei) tree[v].push_back(u);
}
tree[v].push_back(v);
idx[v] = idx[achei];
}
void Joi(int N, int M, int A[], int B[], long long X, int T){
for(int i = 0;i<MAXL;i++){
if(X & (1LL << i)) digito[i] = 1;
else digito[i] = 0;
}
for(int i = 0;i<M;i++){
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
}
bfs();
build_first();
for(int i = MAXL;i<N;i++) extend_tree(lista[i]);
for(int i = 0;i<N;i++) MessageBoard(i, digito[idx[i]] );
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10011;
const int MAXL = 60;
static vector<int> grafo[MAXN],tree[MAXN],lista;
static bitset<MAXN> adjMat[MAXN];
static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],qual_digito[MAXN],relevante[MAXN];
static void bfs(){
memset(contador,0,sizeof(contador));
pai[0] = -1;
contador[0] = 1;
queue<int> fila;
fila.push(0);
while(!fila.empty()){
int v = fila.front();
fila.pop();
lista.push_back(v);
for(int u : grafo[v]){
if(contador[u]) continue;
contador[u] = 1;
pai[u] = v;
fila.push(u);
adjMat[v][u] = 1;
adjMat[u][v] = 1;
}
}
memset(contador,0,sizeof(contador));
}
static void build_first(){
vector<int> primeiro;
for(int i = 0;i<MAXL;i++){
primeiro.push_back(lista[i]);
idx[primeiro.back()] = i;
}
for(int i : primeiro) tree[i] = primeiro;
}
static void extend_tree(int v){
vector<int> copia = tree[pai[v]];
for(int u : copia) relevante[u] = 1;
for(int u : copia){
int w = pai[u];
if(w == -1 || !relevante[w]) continue;
contador[u]++;
contador[w]++;
}
int achei = -1;
for(int u : copia){
if(u == pai[v]) continue;
if(contador[u] == 1){
achei = u;
break;
}
}
for(int u : copia){
contador[u] = 0;
relevante[u] = 0;
if(u != achei) tree[v].push_back(u);
}
tree[v].push_back(v);
idx[v] = idx[achei];
}
static void dfs(int v){
contador[v] = 1;
digito[idx[v]] = qual_digito[v];
for(int u : grafo[v]){
if(!adjMat[u][v] || contador[u] || !relevante[u]) continue;
qual_digito[u] = Move(u);
dfs(u);
Move(v);
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
for(int i = 0;i<M;i++){
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
}
bfs();
build_first();
for(int i = MAXL;i<N;i++) extend_tree(lista[i]);
memset(relevante,0,sizeof(relevante));
for(int i : tree[P]) relevante[i] = 1;
qual_digito[P] = V;
dfs(P);
long long ans = 0;
for(int i = 0;i<MAXL;i++) if(digito[i]) ans += (1LL << i);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2124 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2464 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2860 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3000 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3000 KB |
Output is correct |
| 6 |
Correct |
6 ms |
3000 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3148 KB |
Output is correct |
| 8 |
Correct |
6 ms |
3184 KB |
Output is correct |
| 9 |
Correct |
8 ms |
3200 KB |
Output is correct |
| 10 |
Correct |
6 ms |
3200 KB |
Output is correct |
| 11 |
Correct |
10 ms |
3200 KB |
Output is correct |
| 12 |
Correct |
5 ms |
3200 KB |
Output is correct |
| 13 |
Correct |
7 ms |
3328 KB |
Output is correct |
| 14 |
Correct |
7 ms |
3456 KB |
Output is correct |
| 15 |
Correct |
7 ms |
3460 KB |
Output is correct |
| 16 |
Correct |
6 ms |
3564 KB |
Output is correct |
| 17 |
Correct |
6 ms |
3664 KB |
Output is correct |
| 18 |
Correct |
6 ms |
3664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
34800 KB |
Output is correct |
| 2 |
Correct |
76 ms |
34924 KB |
Output is correct |
| 3 |
Correct |
84 ms |
34936 KB |
Output is correct |
| 4 |
Correct |
60 ms |
34936 KB |
Output is correct |
| 5 |
Correct |
57 ms |
34936 KB |
Output is correct |
| 6 |
Correct |
60 ms |
34936 KB |
Output is correct |
| 7 |
Correct |
61 ms |
34936 KB |
Output is correct |
| 8 |
Correct |
64 ms |
34936 KB |
Output is correct |
| 9 |
Correct |
73 ms |
34936 KB |
Output is correct |
| 10 |
Correct |
62 ms |
34936 KB |
Output is correct |
| 11 |
Correct |
71 ms |
34936 KB |
Output is correct |
| 12 |
Correct |
65 ms |
34936 KB |
Output is correct |
| 13 |
Correct |
64 ms |
34936 KB |
Output is correct |
| 14 |
Correct |
62 ms |
34936 KB |
Output is correct |
| 15 |
Correct |
59 ms |
34936 KB |
Output is correct |
| 16 |
Correct |
61 ms |
34936 KB |
Output is correct |
| 17 |
Correct |
61 ms |
34936 KB |
Output is correct |
| 18 |
Correct |
70 ms |
34936 KB |
Output is correct |
| 19 |
Correct |
60 ms |
34936 KB |
Output is correct |
| 20 |
Correct |
59 ms |
34936 KB |
Output is correct |
| 21 |
Correct |
55 ms |
34936 KB |
Output is correct |
| 22 |
Correct |
72 ms |
34936 KB |
Output is correct |
| 23 |
Correct |
67 ms |
34936 KB |
Output is correct |
| 24 |
Correct |
59 ms |
34936 KB |
Output is correct |
| 25 |
Correct |
57 ms |
34936 KB |
Output is correct |
| 26 |
Correct |
59 ms |
34936 KB |
Output is correct |
| 27 |
Correct |
66 ms |
34936 KB |
Output is correct |
| 28 |
Correct |
61 ms |
34936 KB |
Output is correct |
| 29 |
Correct |
69 ms |
34936 KB |
Output is correct |
| 30 |
Correct |
55 ms |
34936 KB |
Output is correct |
| 31 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 32 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 33 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 34 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 35 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 36 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 37 |
Correct |
7 ms |
34936 KB |
Output is correct |
| 38 |
Correct |
8 ms |
34936 KB |
Output is correct |
| 39 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 40 |
Correct |
7 ms |
34936 KB |
Output is correct |
| 41 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 42 |
Correct |
5 ms |
34936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
34936 KB |
Output is correct |
| 2 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 3 |
Correct |
7 ms |
34936 KB |
Output is correct |
| 4 |
Correct |
13 ms |
34936 KB |
Output is correct |
| 5 |
Correct |
13 ms |
34936 KB |
Output is correct |
| 6 |
Correct |
12 ms |
34936 KB |
Output is correct |
| 7 |
Correct |
13 ms |
34936 KB |
Output is correct |
| 8 |
Correct |
12 ms |
34936 KB |
Output is correct |
| 9 |
Correct |
79 ms |
34936 KB |
Output is correct |
| 10 |
Correct |
56 ms |
34936 KB |
Output is correct |
| 11 |
Correct |
54 ms |
34936 KB |
Output is correct |
| 12 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 13 |
Correct |
4 ms |
34936 KB |
Output is correct |
| 14 |
Correct |
5 ms |
34936 KB |
Output is correct |
| 15 |
Correct |
5 ms |
34936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
34936 KB |
Output is correct |
| 2 |
Correct |
87 ms |
34936 KB |
Output is correct |
| 3 |
Correct |
102 ms |
34936 KB |
Output is correct |
| 4 |
Correct |
81 ms |
34936 KB |
Output is correct |
| 5 |
Correct |
73 ms |
34936 KB |
Output is correct |
| 6 |
Correct |
70 ms |
34936 KB |
Output is correct |
| 7 |
Correct |
62 ms |
34936 KB |
Output is correct |
| 8 |
Correct |
68 ms |
34936 KB |
Output is correct |
| 9 |
Correct |
72 ms |
34936 KB |
Output is correct |
| 10 |
Correct |
75 ms |
34936 KB |
Output is correct |
| 11 |
Correct |
63 ms |
34936 KB |
Output is correct |
| 12 |
Correct |
70 ms |
34936 KB |
Output is correct |
| 13 |
Correct |
72 ms |
34936 KB |
Output is correct |
| 14 |
Correct |
68 ms |
34936 KB |
Output is correct |
| 15 |
Correct |
75 ms |
34936 KB |
Output is correct |
| 16 |
Correct |
64 ms |
34936 KB |
Output is correct |
| 17 |
Correct |
74 ms |
34936 KB |
Output is correct |
| 18 |
Correct |
72 ms |
34936 KB |
Output is correct |
| 19 |
Correct |
74 ms |
34936 KB |
Output is correct |
| 20 |
Correct |
64 ms |
34936 KB |
Output is correct |
| 21 |
Correct |
57 ms |
34936 KB |
Output is correct |
| 22 |
Correct |
65 ms |
34936 KB |
Output is correct |
| 23 |
Correct |
76 ms |
34936 KB |
Output is correct |
| 24 |
Correct |
76 ms |
34936 KB |
Output is correct |
| 25 |
Correct |
69 ms |
34936 KB |
Output is correct |
| 26 |
Correct |
68 ms |
34936 KB |
Output is correct |
| 27 |
Correct |
76 ms |
34936 KB |
Output is correct |
| 28 |
Correct |
61 ms |
34936 KB |
Output is correct |
| 29 |
Correct |
62 ms |
34936 KB |
Output is correct |
| 30 |
Correct |
62 ms |
34936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
34936 KB |
Output is correct |
| 2 |
Correct |
89 ms |
34936 KB |
Output is correct |
| 3 |
Correct |
94 ms |
34936 KB |
Output is correct |
| 4 |
Correct |
68 ms |
34936 KB |
Output is correct |
| 5 |
Correct |
65 ms |
34936 KB |
Output is correct |
| 6 |
Correct |
62 ms |
34936 KB |
Output is correct |
| 7 |
Correct |
62 ms |
34936 KB |
Output is correct |
| 8 |
Correct |
63 ms |
34936 KB |
Output is correct |
| 9 |
Correct |
66 ms |
34936 KB |
Output is correct |
| 10 |
Correct |
65 ms |
34936 KB |
Output is correct |
| 11 |
Correct |
73 ms |
34936 KB |
Output is correct |
| 12 |
Correct |
71 ms |
34936 KB |
Output is correct |
| 13 |
Correct |
65 ms |
34936 KB |
Output is correct |
| 14 |
Correct |
63 ms |
34936 KB |
Output is correct |
| 15 |
Correct |
65 ms |
34936 KB |
Output is correct |
| 16 |
Correct |
64 ms |
34936 KB |
Output is correct |
| 17 |
Correct |
57 ms |
34936 KB |
Output is correct |
| 18 |
Correct |
59 ms |
34936 KB |
Output is correct |
| 19 |
Correct |
60 ms |
34936 KB |
Output is correct |
| 20 |
Correct |
51 ms |
34936 KB |
Output is correct |
| 21 |
Correct |
52 ms |
34936 KB |
Output is correct |
| 22 |
Correct |
69 ms |
34936 KB |
Output is correct |
| 23 |
Correct |
66 ms |
34936 KB |
Output is correct |
| 24 |
Correct |
57 ms |
34936 KB |
Output is correct |
| 25 |
Correct |
57 ms |
34936 KB |
Output is correct |
| 26 |
Correct |
58 ms |
34936 KB |
Output is correct |
| 27 |
Correct |
58 ms |
34936 KB |
Output is correct |
| 28 |
Correct |
64 ms |
34936 KB |
Output is correct |
| 29 |
Correct |
57 ms |
34936 KB |
Output is correct |
| 30 |
Correct |
67 ms |
34936 KB |
Output is correct |
| 31 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 32 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 33 |
Correct |
8 ms |
34936 KB |
Output is correct |
| 34 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 35 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 36 |
Correct |
5 ms |
34936 KB |
Output is correct |
| 37 |
Correct |
4 ms |
34936 KB |
Output is correct |
| 38 |
Correct |
5 ms |
34936 KB |
Output is correct |
| 39 |
Correct |
6 ms |
34936 KB |
Output is correct |
| 40 |
Correct |
5 ms |
34936 KB |
Output is correct |
| 41 |
Correct |
5 ms |
34936 KB |
Output is correct |
| 42 |
Correct |
5 ms |
34936 KB |
Output is correct |
