This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |