#include "Joi.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct node{
int idx = -1, visited = 0, val=0;
vector<int> adj, tree;
} nodes[10069];
vector<int> BinaryConvert(long long X){
vector<int> res;
while(X > 0){
res.pb(X % 2);
X/=2;
}
while(res.size()<60) res.pb(0);
return res;
}
bool connected[10069][10069];
void CopyTree (int target, int neighbor){
int adjCount[10069], cut;
memset(adjCount, 0, sizeof(adjCount));
vector<int> pohon = nodes[neighbor].tree;
for(int i = 0; i < pohon.size() ; i++){
int u = pohon[i];
for(int j = i+1; j< pohon.size(); j++){
int v = pohon[j];
if(connected[u][v]){
adjCount[u]++; adjCount[v]++;
}
}
if(adjCount[u] == 1 && u != neighbor){
cut = u; break;
}
}
vector<int> res;
for(int i = 0; i < pohon.size() ; i++){
if(pohon[i] != cut) res.pb(pohon[i]);
}
res.pb(target);
nodes[target].tree = res;
nodes[target].val = nodes[cut].val;
}
int id=0; vector<int> bit; vector<int> firstTree;
void dfsFirst(int idBefore, int idNow){
if(nodes[idNow].visited == 1 || id>=60) return;
nodes[idNow].visited = 1;
nodes[idNow].idx = id++;
nodes[idNow].val = bit[nodes[idNow].idx % 60];
firstTree.pb(idNow);
for(int i=0;i<nodes[idNow].adj.size();i++){
dfsFirst(idNow, nodes[idNow].adj[i]);
}
nodes[idNow].tree = firstTree;
}
void dfs(int idBefore, int idNow){
if(nodes[idNow].visited == 1) return;
nodes[idNow].visited = 1;
bool atFirst = false;
for(int i=0;i<firstTree.size();i++){
if(firstTree[i] == idNow) atFirst = true;
}
if(!atFirst) CopyTree ( idNow, idBefore);
for(int i=0;i<nodes[idNow].adj.size();i++){
dfs(idNow, nodes[idNow].adj[i]);
}
}
int par[10069];
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) {
memset(connected,0,sizeof(connected));
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])){
nodes[A[i]].adj.pb(B[i]); nodes[B[i]].adj.pb(A[i]);
connected[A[i]][B[i]]= 1; connected[B[i]][A[i]]= 1;
par[findParent(B[i])] = findParent(A[i]);
}
}
//DFS dulu ges di node 0
dfsFirst(-1,0);
for(int i=0;i<N;i++){
MessageBoard(i,nodes[i].val);
}
}
#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){
if(nodes2[idNow].visited) return;
nodes2[idNow].visited=1;
nodes2[idNow].idx = id2++;
nodes2[idNow].before= idBefore;
for(int i=0;i<nodes2[idNow].adj.size();i++){
dfs2(idNow, nodes2[idNow].adj[i]);
}
}
int tt=0;
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){
if(tt==3) if(bit2[nodes2[idNow].idx %60] != -1) return;
if(bit2[now.idx % 60] == -1) countt2++;
bit2[now.idx % 60] = bitInside;
// cout<<now.idx<<" "<<bit2[idNow]<<endl;
nodes2[idNow].counted = 1;
for(int i=0;i<now.adj.size();i++){
if (now.adj[i]==now.before) continue;
if(!nodes2[now.adj[i]].counted) {
if(tt==3) if(bit2[nodes2[now.adj[i]].idx %60] != -1) 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){
if(!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[findParent2(B[i])] = findParent2(A[i]);
}
}
//DFS dulu ges di node 0
dfs2(-1,0);
//Solve
tt=T;
memset(bit2, -1, sizeof(bit2));
solveDFS(P,V);
//Convert to decimal
long long key = 1, res= 0;
for(int i=0;i<60;i++){
res += bit2[i] * key;
key*=2;
}
return res;
}
Compilation message
Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i = 0; i < pohon.size() ; i++){
| ~~^~~~~~~~~~~~~~
Joi.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int j = i+1; j< pohon.size(); j++){
| ~^~~~~~~~~~~~~~
Joi.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0; i < pohon.size() ; i++){
| ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfsFirst(int, int)':
Joi.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<nodes[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<firstTree.size();i++){
| ~^~~~~~~~~~~~~~~~~
Joi.cpp:83:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i=0;i<nodes[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:45:3: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
45 | if(pohon[i] != cut) res.pb(pohon[i]);
| ^~
Ioi.cpp: In function 'void dfs2(int, int)':
Ioi.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | 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 |
43 ms |
109988 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
185 ms |
112116 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
109988 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
112184 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
112164 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
