#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long x;
int t;
int arr[10000];
int p[10000];
vector<int> adj[10000];
typedef pair<int,int> P;
int dist[10000];
int find(int a) {
return p[a]<0?a:p[a]=find(p[a]);
}
void merge(int a,int b) {
a=find(a);
b=find(b);
if (a==b) {
return;
}
p[b]=a;
}
P longest() {
memset(dist,-1,sizeof(dist));
queue<int> q;
q.push(0);
dist[0]=0;
while (!q.empty()) {
int now=q.front();
q.pop();
for(int i=0;i<adj[now].size();i++) {
int nt=adj[now][i];
if (dist[nt]==-1) {
dist[nt]=dist[now]+1;
q.push(nt);
}
}
}
int pos=0;
for(int i=1;i<n;i++) {
if (dist[i]>dist[pos]) {
pos=i;
}
}
memset(dist,-1,sizeof(dist));
dist[pos]=0;
q.push(pos);
while (!q.empty()) {
int now=q.front();
q.pop();
for(int i=0;i<adj[now].size();i++) {
int nt=adj[now][i];
if (dist[nt]==-1) {
dist[nt]=dist[now]+1;
q.push(nt);
}
}
}
int pos1=0;
for(int i=1;i<n;i++) {
if (dist[i]>dist[pos1]) {
pos1=i;
}
}
return P(pos,dist[pos1]);
}
int f=0;
void dfs0(int v,int d,int prev) {
int now=d%60;
if (x&(1LL<<now)) {
MessageBoard(v,1);
}
else {
MessageBoard(v,0);
}
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
dfs0(nt,d+1,v);
}
}
void dfs1(int v,int prev) {
if (f>=60) {
MessageBoard(v,0);
}
else {
if (x&(1LL<<f)) {
MessageBoard(v,1);
}
else {
MessageBoard(v,0);
}
}
f++;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
dfs1(nt,v);
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
n=N;
m=M;
x=X;
t=T;
memset(p,-1,sizeof(p));
for(int i=0;i<m;i++) {
if (find(A[i])!=find(B[i])) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
merge(A[i],B[i]);
}
}
P got=longest();
if (got.second>=59) {
assert(got.first==n-1);
assert(got.second==n-1);
dfs0(got.first,0,-1);
assert(false);
}
else {
assert(t!=3);
dfs1(0,-1);
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int m;
int st,val,t;
int p[10000];
vector<int> adj[10000];
int dist[10000];
typedef pair<int,int> P;
int find(int a) {
return p[a]<0?a:p[a]=find(p[a]);
}
void merge(int a,int b) {
a=find(a);
b=find(b);
if (a==b) {
return;
}
p[b]=a;
}
P longest() {
memset(dist,-1,sizeof(dist));
queue<int> q;
q.push(0);
dist[0]=0;
while (!q.empty()) {
int now=q.front();
q.pop();
for(int i=0;i<adj[now].size();i++) {
int nt=adj[now][i];
if (dist[nt]==-1) {
dist[nt]=dist[now]+1;
q.push(nt);
}
}
}
int pos=0;
for(int i=1;i<n;i++) {
if (dist[i]>dist[pos]) {
pos=i;
}
}
memset(dist,-1,sizeof(dist));
dist[pos]=0;
q.push(pos);
while (!q.empty()) {
int now=q.front();
q.pop();
for(int i=0;i<adj[now].size();i++) {
int nt=adj[now][i];
if (dist[nt]==-1) {
dist[nt]=dist[now]+1;
q.push(nt);
}
}
}
int pos1=0;
for(int i=1;i<n;i++) {
if (dist[i]>dist[pos1]) {
pos1=i;
}
}
return P(pos,dist[pos1]);
}
int par[10000];
int dep[10000];
void dfs(int v,int prev) {
par[v]=prev;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt!=prev) {
dep[nt]=dep[v]+1;
dfs(nt,v);
}
}
}
int f=0;
long long dfs1(int v,int prev) {
long long ret=0;
if (f<60)
ret+=(((long long)val)<<f);
f++;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
bool flag=(f<=59);
if (flag) {
val=Move(nt);
}
ret+=dfs1(nt,v);
if (flag) {
val=Move(v);
}
}
return ret;
}
long long Ioi(int N, int M, int A[], int B[], int PP, int V, int T) {
n=N;
m=M;
st=PP;
val=V;
t=T;
memset(p,-1,sizeof(p));
for(int i=0;i<m;i++) {
if (find(A[i])!=find(B[i])) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
merge(A[i],B[i]);
}
}
P got=longest();
if (got.second>=59) {
assert(got.first==n-1);
assert(got.second==n-1);
dfs(got.first,-1);
while (dep[st]%60!=0) {
val=Move(par[st]);
st=par[st];
}
long long ret=0;
for(int i=0;i<60;i++) {
ret+=(((long long)val)<<i);
if (i==59) {
break;
}
for(int j=0;j<adj[st].size();j++) {
int nt=adj[st][j];
if (nt!=par[st]) {
val=Move(nt);
st=nt;
break;
}
}
}
return ret;
}
else {
assert(t!=3);
dfs(0,-1);
while (st!=0) {
val=Move(par[st]);
st=par[st];
}
return dfs1(0,-1);
}
return 0LL;
}
Compilation message
Joi.cpp: In function 'P longest()':
Joi.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=0;i<adj[now].size();i++) {
| ~^~~~~~~~~~~~~~~~
Joi.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<adj[now].size();i++) {
| ~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs0(int, int, int)':
Joi.cpp:82:18: 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<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs1(int, int)':
Joi.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Ioi.cpp: In function 'P longest()':
Ioi.cpp:34:22: 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<adj[now].size();i++) {
| ~^~~~~~~~~~~~~~~~
Ioi.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<adj[now].size();i++) {
| ~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int dfs1(int, int)':
Ioi.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:138:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int j=0;j<adj[st].size();j++) {
| ~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1260 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
1108 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
9 ms |
2392 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
1108 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
9 ms |
2436 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
2392 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
