#include<bits/stdc++.h>
#define ll long long
#include "Joi.h"
#include "Ioi.h"
using namespace std;
int rod[10005],vel[10005],koji[10005],ostalo;
ll step[65];
bool orgst[10005],koristi[10005];
int N;
vector<int> stablo[10005],S,ubacen[10005];
int getp(int x){
if(rod[x]==x)
return x;
rod[x]=getp(rod[x]);
return rod[x];
}
bool spoj(int a,int b){
a=getp(a);
b=getp(b);
if(a==b)
return false;
if(vel[a]>vel[b])
rod[b]=a;
else{
rod[a]=b;
vel[b]=max(vel[a]+1,vel[b]);
}
return true;
}
void dfs(int gde,int pret){
if(ostalo==0)
return;
//cout<<gde<<" "<<ostalo<<endl;
S.push_back(gde);
ostalo--;
koji[gde]=ostalo;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs(stablo[gde][i],gde);
return;
}
pair<int,int> najdalji(int gde,int pret,bool ex=false){
if(koristi[gde]==false and ex==false)
return {gde,0};
int d=0;
pair<int,int> ret={gde,1},pp;
for(int i=0;i<stablo[gde].size();i++){
if(stablo[gde][i]==pret)
continue;
pp=najdalji(stablo[gde][i],gde);
if(pp.second>d){
d=pp.second;
ret=pp;
ret.second++;
}
}
return ret;
}
void dfs2(int gde,int pret,vector<int> ust){
if(orgst[gde])
return;
for(int i=0;i<ust.size();i++)
koristi[ust[i]]=true;
pair<int,int> pp =najdalji(gde,gde,true);
int najd=pp.first;
// cout<<gde<<" "<<pret<<" najdalji "<<najd<<endl;
for(int i=0;i<ust.size();i++)
if(ust[i]==najd){
swap(ust[i],ust[ust.size()-1]);
ust.pop_back();
break;
}
ust.push_back(gde);
ubacen[gde]=ust;
koji[gde]=koji[najd];
koristi[najd]=false;
for(int i=0;i<ust.size();i++)
koristi[ust[i]]=false;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs2(stablo[gde][i],gde,ust);
}
void init(int n,int M,int A[],int B[]){
N=n;
for(int i=0;i<N;i++){
rod[i]=i;
vel[i]=0;
}
for(int i=0;i<M;i++){
if(!spoj(A[i],B[i]))
continue;
stablo[A[i]].push_back(B[i]);
stablo[B[i]].push_back(A[i]);
}
ostalo=60;
dfs(0,0);
for(int i=0;i<S.size();i++){
orgst[S[i]]=true;
ubacen[S[i]]=S;
}
for(int i=0;i<S.size();i++){
for(int j=0;j<stablo[S[i]].size();j++)
dfs2(stablo[S[i]][j],S[i],S);
}
step[0]=1;
for(int i=1;i<=59;i++)
step[i]=step[i-1]<<1;
}
void Joi(int n, int M, int A[], int B[], long long X, int T) {
init(n,M,A,B);
for(int i=0;i<N;i++)
MessageBoard(i,(step[koji[i]]&X)!=0);
return;
}
#include<bits/stdc++.h>
#define ll long long
#include "Joi.h"
#include "Ioi.h"
using namespace std;
int rod[10005],vel[10005],koji[10005],ostalo;
ll step[65];
bool orgst[10005],koristi[10005];
int N;
vector<int> stablo[10005],S,ubacen[10005];
int getp(int x){
if(rod[x]==x)
return x;
rod[x]=getp(rod[x]);
return rod[x];
}
bool spoj(int a,int b){
a=getp(a);
b=getp(b);
if(a==b)
return false;
if(vel[a]>vel[b])
rod[b]=a;
else{
rod[a]=b;
vel[b]=max(vel[a]+1,vel[b]);
}
return true;
}
void dfs(int gde,int pret){
if(ostalo==0)
return;
//cout<<gde<<" "<<ostalo<<endl;
S.push_back(gde);
ostalo--;
koji[gde]=ostalo;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs(stablo[gde][i],gde);
return;
}
pair<int,int> najdalji(int gde,int pret,bool ex=false){
if(koristi[gde]==false and ex==false)
return {gde,0};
int d=0;
pair<int,int> ret={gde,1},pp;
for(int i=0;i<stablo[gde].size();i++){
if(stablo[gde][i]==pret)
continue;
pp=najdalji(stablo[gde][i],gde);
if(pp.second>d){
d=pp.second;
ret=pp;
ret.second++;
}
}
return ret;
}
void dfs2(int gde,int pret,vector<int> ust){
if(orgst[gde])
return;
for(int i=0;i<ust.size();i++)
koristi[ust[i]]=true;
pair<int,int> pp =najdalji(gde,gde,true);
int najd=pp.first;
// cout<<gde<<" "<<pret<<" najdalji "<<najd<<endl;
for(int i=0;i<ust.size();i++)
if(ust[i]==najd){
swap(ust[i],ust[ust.size()-1]);
ust.pop_back();
break;
}
ust.push_back(gde);
ubacen[gde]=ust;
koji[gde]=koji[najd];
koristi[najd]=false;
for(int i=0;i<ust.size();i++)
koristi[ust[i]]=false;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs2(stablo[gde][i],gde,ust);
}
void init(int n,int M,int A[],int B[]){
N=n;
for(int i=0;i<N;i++){
rod[i]=i;
vel[i]=0;
}
for(int i=0;i<M;i++){
if(!spoj(A[i],B[i]))
continue;
stablo[A[i]].push_back(B[i]);
stablo[B[i]].push_back(A[i]);
}
ostalo=60;
dfs(0,0);
for(int i=0;i<S.size();i++){
orgst[S[i]]=true;
ubacen[S[i]]=S;
}
for(int i=0;i<S.size();i++){
for(int j=0;j<stablo[S[i]].size();j++)
dfs2(stablo[S[i]][j],S[i],S);
}
step[0]=1;
for(int i=1;i<=59;i++)
step[i]=step[i-1]<<1;
}
int broj[10005];
int poz;
void dfs3(int gde,int pret){
if(!koristi[gde])
return;
if(poz!=gde){
broj[gde]=Move(gde);
poz=gde;
}
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs3(stablo[gde][i],gde);
if(poz!=gde){
broj[gde]=Move(gde);
poz=gde;
}
return;
}
long long Ioi(int n, int M, int A[], int B[], int P, int V, int T) {
init(n,M,A,B);
broj[P]=V;
poz=P;
for(int i=0;i<ubacen[P].size();i++)
koristi[ubacen[P][i]]=true;
dfs3(P,P);
ll res=0;
for(int i=0;i<ubacen[P].size();i++)
res+=broj[ubacen[P][i]]*step[koji[ubacen[P][i]]];
return res;
}
Compilation message
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<stablo[gde].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'std::pair<int, int> najdalji(int, int, bool)':
Joi.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<stablo[gde].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs2(int, int, std::vector<int>)':
Joi.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i=0;i<ust.size();i++)
| ~^~~~~~~~~~~
Joi.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0;i<ust.size();i++)
| ~^~~~~~~~~~~
Joi.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0;i<ust.size();i++)
| ~^~~~~~~~~~~
Joi.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=0;i<stablo[gde].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void init(int, int, int*, int*)':
Joi.cpp:98:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
Joi.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
Joi.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int j=0;j<stablo[S[i]].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<stablo[gde].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'std::pair<int, int> najdalji(int, int, bool)':
Ioi.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<stablo[gde].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int, int, std::vector<int>)':
Ioi.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i=0;i<ust.size();i++)
| ~^~~~~~~~~~~
Ioi.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0;i<ust.size();i++)
| ~^~~~~~~~~~~
Ioi.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0;i<ust.size();i++)
| ~^~~~~~~~~~~
Ioi.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=0;i<stablo[gde].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void init(int, int, int*, int*)':
Ioi.cpp:98:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
Ioi.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
Ioi.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int j=0;j<stablo[S[i]].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs3(int, int)':
Ioi.cpp:119:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i=0;i<stablo[gde].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int i=0;i<ubacen[P].size();i++)
| ~^~~~~~~~~~~~~~~~~
Ioi.cpp:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i=0;i<ubacen[P].size();i++)
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1536 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
8836 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1792 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
8768 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
8864 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
