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 <bits/stdc++.h>
#include "Joi.h"
using namespace std;
const int maxn = 1e5 + 100;
vector<int> e[maxn];
int n;
int parent[maxn];
int h[maxn];
int get(int x){
return x == parent[x] ? x : parent[x] = get(parent[x]);
}
bool uni(int x, int y){
x = get(x);
y = get(y);
if (x == y)
return 0;
parent[x] = y;
return 1;
}
int poi[maxn];
void predfs(int v, int par){
for (auto i : e[v])
if (i != par)
poi[i] = v, h[i] = h[v] + 1, predfs(i, v);
}
pair<int, int> mas[maxn];
vector<int> q[maxn];
int pos[maxn];
bool good[maxn];
void make(int v, int par, int st){
q[st].push_back(v);
for (auto i : e[v])
if (i != par && good[i])
make(i, v, st);
}
void Joi(int N, int M, int A[], int B[], long long X, int T){
n = N;
for (int i = 0; i < n; i++)
parent[i] = i;
for (int i = 0; i < M; i++)
if (uni(A[i], B[i])){
e[A[i]].push_back(B[i]);
e[B[i]].push_back(A[i]);
}
predfs(0, -1);
for (int i = 0; i < n; i++)
mas[i] = make_pair(h[i], i);
sort(mas, mas + n);
for (int i = 0; i < 60; i++)
good[mas[i].second] = 1, pos[mas[i].second] = i;
for (int i = 0; i < 60; i++)
make(mas[i].second, -1, mas[i].second);
for (int i1 = 60; i1 < n; i1++){
int i = mas[i1].second;
int v = poi[i];
q[i] = q[v];
pos[i] = pos[q[i].back()];
q[i].pop_back();
q[i].insert(q[i].begin(), i);
}
for (int i = 0; i < n; i++)
MessageBoard(i, ((1ll << pos[i]) & X) > 0);
}
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
const int maxn = 1e5 + 100;
vector<int> e[maxn];
int n;
int parent[maxn];
int h[maxn];
int get(int x){
return x == parent[x] ? x : parent[x] = get(parent[x]);
}
bool uni(int x, int y){
x = get(x);
y = get(y);
if (x == y)
return 0;
parent[x] = y;
return 1;
}
int poi[maxn];
void predfs(int v, int par){
for (auto i : e[v])
if (i != par)
poi[i] = v, h[i] = h[v] + 1, predfs(i, v);
}
pair<int, int> mas[maxn];
vector<int> q[maxn];
int pos[maxn];
bool good[maxn];
void make(int v, int par, int st){
q[st].push_back(v);
for (auto i : e[v])
if (i != par && good[i])
make(i, v, st);
}
long long ans;
int s[60];
void go(int v, int par, vector<int> &g, int &id, int val){
s[pos[v]] = val;
if (id < 60){
for (auto i : e[v])
if (i == g[id]){
id++, go(i, v, g, id, Move(i));
go(v, par, g, id, val);
return;
}
}
if (par != -1)
Move(par);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
n = N;
for (int i = 0; i < n; i++)
parent[i] = i;
for (int i = 0; i < M; i++)
if (uni(A[i], B[i])){
e[A[i]].push_back(B[i]);
e[B[i]].push_back(A[i]);
}
predfs(0, -1);
for (int i = 0; i < n; i++)
mas[i] = make_pair(h[i], i);
sort(mas, mas + n);
for (int i = 0; i < 60; i++)
good[mas[i].second] = 1, pos[mas[i].second] = i;
for (int i = 0; i < 60; i++)
make(mas[i].second, -1, mas[i].second);
for (int i1 = 60; i1 < n; i1++){
int i = mas[i1].second;
int v = poi[i];
q[i] = q[v];
pos[i] = pos[q[i].back()];
q[i].pop_back();
q[i].insert(q[i].begin(), i);
}
int ss = 1;
go(P, -1, q[P], ss, V);
for (int i = 0; i < 60; i++)
ans += (1ll << i) * s[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... |