oj.uz

Submission #854770

# Submission time Handle Problem Language Result Execution time Memory
854770 2023-09-28T20:10:00 Z epicci23 Amusement Park (JOI17_amusement_park) C++17
0 / 100
 11 ms 3792 KB 
#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++){
    a[i]++;b[i]++;
    v[a[i]].pb(b[i]);
    v[b[i]].pb(a[i]);
  }
  
  X=x;
  dfs(1);
  calc(1,1);
  
  if(dp[1]>=60) make1(1,1,0);
  else make2(1,1);
}

#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!=1) 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++){
    a[i]++;b[i]++;
    v[a[i]].pb(b[i]);
    v[b[i]].pb(a[i]);
  }
  par[1]=1;
  dfs(1);
  calc(1,1);
  
  if(dp[1]>=60) make1(1,1,0);
  else make2(1,1);
  
  if(cur) X|=1<<wh[p];
  vis2[wh[p]]=1;
  
  int c=p;
  while(c!=1){
    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[1]>=60) calc1(1,0,cur);
  else calc2(1,0,cur);
  
  return X;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1880 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3668 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1812 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3792 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3680 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -