#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[1069][1069];
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;
nodes[target].idx = nodes[cut].idx;
}
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);
else nodes[idNow].tree = firstTree;
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,false,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]]= true; connected[B[i]][A[i]]= true;
par[findParent(B[i])] = findParent(A[i]);
}
}
//DFS dulu ges di node 0
dfsFirst(-1,0);
for(int i=0;i<N;i++) nodes[i].visited=0;
dfs(-1,0);
for(int i=0;i<N;i++){
// cout<<i<<" : "<<nodes[i].val<<endl;
MessageBoard(i,nodes[i].val);
}
}
#include "Ioi.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;
} nodes2[10069];
bool connected2[1069][1069];
void CopyTree2 (int target, int neighbor){
int adjCount[10069], cut;
memset(adjCount, 0, sizeof(adjCount));
vector<int> pohon = nodes2[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(connected2[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);
nodes2[target].tree = res;
nodes2[target].idx = nodes2[cut].idx;
}
int id2=0, bit2[60];
vector<int> firstTree2;
void dfsFirst2(int idBefore, int idNow){
if(nodes2[idNow].visited == 1 || id2>=60) return;
nodes2[idNow].visited = 1;
nodes2[idNow].idx = id2++;
firstTree2.pb(idNow);
for(int i=0;i<nodes2[idNow].adj.size();i++){
dfsFirst2(idNow, nodes2[idNow].adj[i]);
}
nodes2[idNow].tree = firstTree2;
}
int tt=0;
void dfs2(int idBefore, int idNow){
if(nodes2[idNow].visited == 1) return;
nodes2[idNow].visited = 1;
bool atFirst = false;
for(int i=0;i<firstTree2.size();i++){
if(firstTree2[i] == idNow) atFirst = true;
}
if(!atFirst) CopyTree2 ( idNow, idBefore);
else nodes2[idNow].tree = firstTree2;
for(int i=0;i<nodes2[idNow].adj.size();i++){
dfs2(idNow, nodes2[idNow].adj[i]);
}
}
void solveDFS(int idNow, int bitValue){
nodes2[idNow].visited = 1;
bit2[nodes2[idNow].idx]= bitValue;
for(int i=0;i<nodes2[idNow].adj.size();i++){
int idNext = nodes2[idNow].adj[i];
if(!nodes2[idNext].visited){
solveDFS(idNext, Move(idNext));
Move(idNow);
}
}
}
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) {
memset(connected2,false,sizeof(connected2));
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]);
connected2[A[i]][B[i]]= true; connected2[B[i]][A[i]]= true;
par2[findParent2(B[i])] = findParent2(A[i]);
}
}
//DFS dulu ges di node 0
dfsFirst2(-1,0);
for(int i=0;i<N;i++) nodes2[i].visited=0;
dfs2(-1,0);
//Solve
for(int i=0;i<nodes2[P].tree.size();i++) nodes2[nodes2[P].tree[i]].visited=0;
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:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 0; i < pohon.size() ; i++){
| ~~^~~~~~~~~~~~~~
Joi.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int j = i+1; j< pohon.size(); j++){
| ~^~~~~~~~~~~~~~
Joi.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0; i < pohon.size() ; i++){
| ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfsFirst(int, int)':
Joi.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=0;i<nodes[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:80:16: 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<firstTree.size();i++){
| ~^~~~~~~~~~~~~~~~~
Joi.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=0;i<nodes[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void CopyTree(int, int)':
Joi.cpp:46:3: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
46 | if(pohon[i] != cut) res.pb(pohon[i]);
| ^~
Ioi.cpp: In function 'void CopyTree2(int, int)':
Ioi.cpp:19:19: 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 < pohon.size() ; i++){
| ~~^~~~~~~~~~~~~~
Ioi.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int j = i+1; j< pohon.size(); j++){
| ~^~~~~~~~~~~~~~
Ioi.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i = 0; i < pohon.size() ; i++){
| ~~^~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfsFirst2(int, int)':
Ioi.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<nodes2[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int, int)':
Ioi.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<firstTree2.size();i++){
| ~^~~~~~~~~~~~~~~~~~
Ioi.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0;i<nodes2[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void solveDFS(int, int)':
Ioi.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i=0;i<nodes2[idNow].adj.size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:117:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=0;i<nodes2[P].tree.size();i++) nodes2[nodes2[P].tree[i]].visited=0;
| ~^~~~~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void CopyTree2(int, int)':
Ioi.cpp:35:3: warning: 'cut' may be used uninitialized in this function [-Wmaybe-uninitialized]
35 | if(pohon[i] != cut) res.pb(pohon[i]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4356 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4360 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4364 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4344 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4356 KB |
Output is correct |
| 7 |
Correct |
4 ms |
4360 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4356 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4368 KB |
Output is correct |
| 10 |
Correct |
4 ms |
4364 KB |
Output is correct |
| 11 |
Correct |
7 ms |
4512 KB |
Output is correct |
| 12 |
Correct |
2 ms |
4096 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4368 KB |
Output is correct |
| 14 |
Correct |
4 ms |
4364 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4364 KB |
Output is correct |
| 16 |
Correct |
4 ms |
4360 KB |
Output is correct |
| 17 |
Correct |
4 ms |
4360 KB |
Output is correct |
| 18 |
Correct |
4 ms |
4364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
4844 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4364 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4316 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4364 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
4100 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
4924 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
4820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
