Submission #854773

#	Time	Username	Problem	Language	Result	Execution time	Memory
854773		epicci23	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	19 ms	5876 KiB

Joi

#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back

const int N = 1e4 + 5;

vector<int> v[N];
int dp[N];
vector<int> tree[N];
int vis[N];
int timer=0;
long long X;

void dfs(int c){
  vis[c]=1;
  for(int x:v[c]){
    if(vis[x]) continue;
    tree[c].pb(x);
    tree[x].pb(c);
    dfs(x);
  }
}

void calc(int c,int p){
  for(int x:tree[c]){
    if(x==p) continue;
    calc(x,c);
    dp[c]=max(dp[c],dp[x]);
  }
  dp[c]++;
}

void make1(int c,int p,int d){
  int u=X>>d&1;
  MessageBoard(c,u);
  for(int x:tree[c]){
    if(x==p) continue; 
    make1(x,c,(d+1)%60);
  }
}

void make2(int c,int p){
  int u=X>>timer&1;
  MessageBoard(c,u);
  timer++;
  for(int x:tree[c]){
    if(x==p) continue;
    make2(x,c);
  }
}

void Joi(int n, int m, int a[], int b[], long long x, int t){

  for(int i=0;i<m;i++){
    v[a[i]].pb(b[i]);
    v[b[i]].pb(a[i]);
  }

  X=x;
  dfs(0);
  calc(0,0);
  
  if(dp[0]>=60) make1(0,0,0);
  else make2(0,0);
}

Ioi

#include "Ioi.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back

const int N = 1e4 + 5;

vector<int> v[N];
int dp[N];
vector<int> vis2(60,0);
vector<int> tree[N];
int par[N];
int vis[N];
int wh[N];
int timer=0;
long long X;

void dfs(int c){
  vis[c]=1;
  for(int x:v[c]){
    if(vis[x]) continue;
    par[x]=c;
    tree[c].pb(x);
    tree[x].pb(c);
    dfs(x);
  }
}

void calc(int c,int p){
  for(int x:tree[c]){
    if(x==p) continue;
    calc(x,c);
    dp[c]=max(dp[c],dp[x]);
  }
  dp[c]++;
}

void make1(int c,int p,int d){
  wh[c]=d;
  for(int x:tree[c]){
    if(x==p) continue; 
    make1(x,c,(d+1)%60);
  }
}

void make2(int c,int p){
  wh[c]=timer;
  timer=(timer+1)%60;
  for(int x:tree[c]){
    if(x==p) continue;
    make2(x,c);
  }
}

void calc1(int c,int p,int cu){
  if(cu) X|=1<<wh[c];
  vis2[wh[c]]=1;
  if(count(vis2.begin(), vis2.end(),1)==60) return;

  for(int x:tree[c]){
    if(x==p) continue;
    if(dp[c]-1!=dp[x]) continue;
    calc1(x,c,move(x));
    if(count(vis2.begin(), vis2.end(),1)==60) return;
  }
}

void calc2(int c,int p,int cu){
  if(cu) X|=1<<wh[c];
  vis2[wh[c]]=1;
  if(count(vis2.begin(), vis2.end(),1)==60) return;

  for(int x:tree[c]){
    if(x==p) continue;
    calc2(x,c,move(x));
    if(count(vis2.begin(), vis2.end(),1)==60) return;
  }
  if(count(vis2.begin(), vis2.end(),1)==60) return;
  if(c!=0) move(p);
}

long long Ioi(int n, int m, int a[], int b[], int p, int cur, int t) {
  for(int i=0;i<m;i++){
    v[a[i]].pb(b[i]);
    v[b[i]].pb(a[i]);
  }
  par[0]=0;
  dfs(0);
  calc(0,0);
  
  if(dp[0]>=60) make1(0,0,0);
  else make2(0,0);
  
  if(cur) X|=1<<wh[p];
  vis2[wh[p]]=1;
  
  int c=p;
  while(c!=0){
    cur=move(par[c]);
    c=par[c];
    if(cur) X|=1<<wh[c];
    vis2[wh[c]]=1;
    if(count(vis2.begin(), vis2.end(),1)==60) return X;
  }
  
  if(dp[0]>=60) calc1(0,0,cur);
  else calc2(0,0,cur);
  
  return X;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17