#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
int idx = -1, visited = 0, val=0, before;
vector<int> adj;
} nodes[200069];
vector<int> BinaryConvert(long long X){
vector<int> res;
while(X > 0){
res.push_back(X % 2);
X/=2;
}
while(res.size()<60) res.push_back(0);
return res;
}
int id=0; vector<int> bit;
void dfs(int idBefore, int idNow){
node now= nodes[idNow];
if(now.visited == 1) return;
nodes[idNow].visited = 1;
nodes[idNow].idx = id++;
nodes[idNow].val = bit[nodes[idNow].idx % 60];
// cout<<"Message "<<nodes[idNow].idx<< " : "<<nodes[idNow].val<<endl;
MessageBoard(idNow, nodes[idNow].val);
nodes[idNow].before= idBefore;
for(int i=0;i<nodes[idNow].adj.size();i++){
dfs(idNow, nodes[idNow].adj[i]);
}
}
int par[200069];
int findParent(int x){
if(x==par[x]) return x;
return findParent(par[x]);
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
bit = BinaryConvert(X);
for(int i=0;i<N;i++) par[i]=i;
for(int i=0;i<M;i++){
if(findParent(A[i])!=findParent(B[i])){
// cout<<A[i]<<" - "<<B[i]<<endl;
nodes[A[i]].adj.push_back(B[i]);
nodes[B[i]].adj.push_back(A[i]);
par[B[i]] = findParent(A[i]);
}
}
//DFS dulu ges di node 0
dfs(-1,0);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
struct node2{
int idx = -1, visited = 0, val, before=-1, counted = 0;
vector<int> adj;
} nodes2[200069];
int id2=0, bit2[60], countt2=0;
void dfs2(int idBefore, int idNow){
node2 now= nodes2[idNow];
if(nodes2[idNow].visited) return;
nodes2[idNow].visited=1;
nodes2[idNow].idx = id2++;
// cout<<idNow<<" "<<nodes2[idNow].idx<<endl;
nodes2[idNow].before= idBefore;
for(int i=0;i<nodes2[idNow].adj.size();i++){
dfs2(idNow, nodes2[idNow].adj[i]);
}
}
void solveDFS(int idNow, int bitInside){
node2 now = nodes2[idNow];
// cout<<now.idx<<endl;
// cout<<"track count: "<<countt2<<"and now.before "<<now.before<<endl;
if(!nodes2[idNow].counted){
bit2[now.idx % 60] = bitInside;
// cout<<now.idx<<" "<<bit2[idNow]<<endl;
nodes2[idNow].counted = 1; countt2++;
for(int i=0;i<now.adj.size();i++){
if (now.adj[i]==now.before) continue;
solveDFS(now.adj[i], Move(now.adj[i]));
if(countt2<60) Move(idNow);
else return;
}
//kalau uda cek semua anak"nya ya pindah ke ibunya diatas 1
// if(idNow==5) cout<<"before 5"<<now.before<<endl;
if(now.before != -1 && !nodes2[now.before].counted && countt2<60){
// cout<<"use here";
solveDFS(now.before, Move(now.before));
}
}
}
int par2[200069];
int findParent2(int x){
if(x==par2[x]) return x;
return findParent2(par2[x]);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
for(int i=0;i<N;i++) par2[i]=i;
for(int i=0;i<M;i++){
if(findParent2(A[i])!=findParent2(B[i])){
nodes2[A[i]].adj.push_back(B[i]);
nodes2[B[i]].adj.push_back(A[i]);
par2[A[i]] = findParent2(B[i]);
}
}
//DFS dulu ges di node 0
dfs2(-1,0);
//Solve
memset(bit2, -1, sizeof(bit2));
solveDFS(P,V);
//Convert to decimal
long long key = 1, res= 0;
// cout<<endl;
for(int i=0;i<60;i++){
// cout<<bit2[i];
res += bit2[i] * key;
key*=2;
}
return res;
}
Compilation message
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0;i<nodes[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int, int)':
Ioi.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<nodes2[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void solveDFS(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<now.adj.size();i++){
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
17936 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
21784 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
17936 KB |
Output is correct |
| 2 |
Correct |
10 ms |
17936 KB |
Output is correct |
| 3 |
Correct |
9 ms |
17936 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
18604 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
21900 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
21860 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
