oj.uz

답안 #854781

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854781 2023-09-28T21:16:20 Z epicci23 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 20 ms 5980 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&1LL;
  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&1LL;
  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);
}

#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|=1LL<<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|=1LL<<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|=1LL<<wh[p];
  vis2[wh[p]]=1;
  
  int c=p;
  while(c!=0){
    cur=move(par[c]);
    c=par[c];
    if(cur) X|=1LL<<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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1816 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 5476 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1804 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 5744 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 5980 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -