#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;
}
//assert(nt==v-1);
dfs0(nt,d+1,v);
}
}
void dfs1(int v,int prev) {
int now=f%60;
if (x&(1LL<<now)) {
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]);
}
}
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];
int ind[10000];
int rev[10000];
int sz[10000];
int md[10000];
int f=0;
void dfs(int v,int prev) {
par[v]=prev;
md[v]=dep[v];
sz[v]=1;
ind[v]=f++;
rev[ind[v]]=v;
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);
md[v]=max(md[v],md[nt]);
sz[v]+=sz[nt];
}
}
}
bool need[10000];
long long chk[60];
void dfs1(int v,int prev) {
chk[ind[v]%60]=val;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev||!need[nt]) {
continue;
}
val=Move(nt);
dfs1(nt,v);
val=Move(v);
}
}
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]);
}
}
int now=st;
int pr=-1;
while (sz[now]<60) {
pr=now;
now=par[now];
}
need[now]=true;
int l=ind[now];
int r=ind[now]+sz[now]-1;
int vst=0;
if (pr==-1) {
vst=l;
}
else {
int ll=ind[pr];
int rr=ind[pr]+sz[pr]-1;
while (rr-ll<59) {
if (ll!=l) {
ll--;
}
else if (rr!=r) {
rr++;
}
}
vst=ll;
}
for(int i=vst;i<vst+60;i++) {
need[rev[i]]=true;
}
dfs1(st,-1);
long long ret=0;
for(int i=0;i<60;i++) {
ret+=(chk[i]<<i);
}
return ret;
}
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:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | 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:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs1(int, int)':
Ioi.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3098 ms |
1168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3010 ms |
3144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3049 ms |
1152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3074 ms |
3128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3009 ms |
3084 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
