#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
int distJ[10010];
bool odwJ[10010];
int fatherJ[10010], ojciecJ[10010];
vector<int>grafJ[10010];
int findJ(int x){
if(fatherJ[x]==x)return x;
return fatherJ[x] = findJ(fatherJ[x]);
}
int preorder[10010], preorder2[10010];
int preitJ;
void dfs(int x, int o){
preorder[x] = preitJ++;
for(auto j: grafJ[x])
if(j!=o)
dfs(j, x);
}
void dfs2(int x, int o){
preorder2[x] = preitJ++;
for(auto j: grafJ[x])
if(j!=o && preorder[j]<60)
dfs2(j, x);
}
void Joi(int n, int m, int a[], int b[], long long x, int t) {
//printf("Joi\n");
//f&u zeby zrobic drzewo
int i;
for(i=0;i<n;i++)fatherJ[i] = i;
for(i=0;i<m;i++){
if(findJ(a[i])!=findJ(b[i])){
grafJ[a[i]].push_back(b[i]), grafJ[b[i]].push_back(a[i]);
fatherJ[fatherJ[a[i]]] = fatherJ[b[i]];
}
}
queue<int>kolejka;
kolejka.push(0);
distJ[0] = 1;
int w;
while(kolejka.size()){
w = kolejka.front();
kolejka.pop();
for(auto j: grafJ[w])
if(distJ[j]==0){
distJ[j] = distJ[w]+1;
kolejka.push(j);
}
}
for(i=0;i<n;i++){
distJ[i] = 0;
}
kolejka.push(w);
distJ[w] = 1;
int k = w;
while(kolejka.size()){
w = kolejka.front();
kolejka.pop();
for(auto j: grafJ[w])
if(distJ[j]==0){
distJ[j] = distJ[w]+1;
kolejka.push(j);
}
}
if(distJ[w]>=60){
//printf("Case 1\n");
for(i=0;i<n;i++){
int pom = distJ[i]-1;
pom = pom%60;
MessageBoard(i, (x>>pom)&1);
}
return;
}
else{
//printf("Case 2\n");
int pom1 = ojciecJ[w], pom2 = w;
while(pom1!=-1){
for(int i=0;i<(int)grafJ[pom1].size();i++)
if(grafJ[pom1][i]==pom2){
swap(grafJ[pom1][i], grafJ[pom1][0]);
break;
}
pom2 = pom1;
pom1 = ojciecJ[pom1];
}
dfs(k, k);
pom1 = ojciecJ[w], pom2 = w;
while(pom1!=-1){
for(auto &ij: grafJ[pom1])
if(ij==pom2){
swap(ij, grafJ[pom1].back());
break;
}
pom2 = pom1;
pom1 = ojciecJ[pom1];
}
preitJ=0;
dfs2(k, k);
for(i=0;i<n;i++){
if(preorder2[i]<60)
MessageBoard(i, (x>>preorder2[i])&1);
else
MessageBoard(i, 0);
}
return;
}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
int dist[10010];
bool odw[10010];
int father[10010];
int ojciec[10010];
vector<int>graf[10010];
int find(int x){
if(father[x]==x)return x;
return father[x] = find(father[x]);
}
long long wynik = 0;
int preit=0;
int preorderI[10010];
void dfs1(int x, int o){
for(auto j: graf[x])
if(o!=j && preorderI[j]<60){
if(preit<60)
wynik+=(1ll<<preit++)*Move(j);
dfs1(j, x);
}
if(preit<60)
int skip = Move(o);
}
void dfs3(int x, int o){
preorderI[x] = preit++;
for(auto j: graf[x])
if(j!=o)
dfs3(j, x);
}
long long Ioi(int n, int m, int a[], int b[], int p, int v, int t) {
//printf("Ioi:\n");
//f&u zeby zrobic drzewo
int i;
for(i=0;i<n;i++)father[i] = i;
for(i=0;i<m;i++){
if(find(a[i])!=find(b[i])){
graf[a[i]].push_back(b[i]), graf[b[i]].push_back(a[i]);
father[father[a[i]]] = father[b[i]];
}
}
queue<int>kolejka;
kolejka.push(0);
dist[0] = 1;
int w;
while(kolejka.size()){
w = kolejka.front();
kolejka.pop();
for(auto j: graf[w])
if(dist[j]==0){
dist[j] = dist[w]+1;
kolejka.push(j);
}
}
for(i=0;i<n;i++){
dist[i] = 0;
}
kolejka.push(w);
dist[w] = 1;
ojciec[w] = -1;
int k = w;
while(kolejka.size()){
w = kolejka.front();
kolejka.pop();
for(auto j: graf[w])
if(dist[j]==0){
ojciec[j] = w;
dist[j] = dist[w]+1;
kolejka.push(j);
}
}
if(dist[w]>=60){
//printf("Case 1\n");
//return 0;
while((dist[p]-1)%60!=0){
p = ojciec[p];
v = Move(p);
}
long long res = 0;
long long pom = 0;
if(ojciec[p]==-1){
res = v;
vector<int>vec;
while(dist[w]>60)w = ojciec[w];
while(w!=p){
vec.push_back(w);
w = ojciec[w];
}
reverse(vec.begin(), vec.end());
for(auto j: vec){
pom++;
res = res + (1ll<<pom)*Move(j);
}
}
else{
for(i=59;i>=0;i--){
res = res + (1ll<<i)*Move(ojciec[p]);
p = ojciec[p];
}
}
//printf("res: %lld\n", res);
return res;
}
else{
//return 0;
//printf("Case 2\n");
while(ojciec[p]!=-1){
v = Move(ojciec[p]);
p = ojciec[p];
}
int pom1 = ojciec[w], pom2 = w;
while(pom1!=-1){
for(int i=0;i<(int)graf[pom1].size();i++)
if(graf[pom1][i]==pom2){
swap(graf[pom1][i], graf[pom1][0]);
break;
}
pom2 = pom1;
pom1 = ojciec[pom1];
}
dfs3(k, k);
pom1 = ojciec[w], pom2 = w;
while(pom1!=-1){
for(auto &ij: graf[pom1])
if(ij==pom2){
swap(ij, graf[pom1].back());
break;
}
pom2 = pom1;
pom1 = ojciec[pom1];
}
preit = 1;
wynik=v;
dfs1(p, p);
return wynik;
}
}
Compilation message
Ioi.cpp: In function 'void dfs1(int, int)':
Ioi.cpp:24:7: warning: unused variable 'skip' [-Wunused-variable]
24 | int skip = Move(o);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
604 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
3884 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3744 KB |
Output is correct |
| 3 |
Correct |
19 ms |
3764 KB |
Output is correct |
| 4 |
Execution timed out |
3081 ms |
1368 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1300 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1312 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1312 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1432 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1352 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1352 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1328 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1352 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2840 KB |
Output is correct |
| 10 |
Correct |
7 ms |
2872 KB |
Output is correct |
| 11 |
Correct |
7 ms |
2880 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1312 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1316 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
3872 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3872 KB |
Output is correct |
| 3 |
Correct |
14 ms |
3876 KB |
Output is correct |
| 4 |
Execution timed out |
3042 ms |
1368 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
3896 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3952 KB |
Output is correct |
| 3 |
Correct |
13 ms |
3760 KB |
Output is correct |
| 4 |
Execution timed out |
3055 ms |
1372 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
