제출 #1169994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169994		fryingduc	Amusement Park (JOI17_amusement_park)	C++20	70 / 100	16 ms	2120 KiB

Joi

#include "Joi.h"
#include "bits/stdc++.h"

using namespace std;

namespace {
  const int maxn = 1e4 + 4;
  vector<int> g[maxn];
  vector<int> adj[maxn];
  int n;
  int par[maxn];
  int h[maxn];
  int tin[maxn], timer, et[maxn];
  int sz[maxn];
  
  pair<int, int> bfs(int src) {
    queue<int> q;
    vector<int> d(n + 1, -1);
    d[src] = 0;
    par[src] = 0;
    q.push(src);
    memset(par, -1, sizeof(par));
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (d[v] == -1) {
          d[v] = d[u] + 1;
          par[v] = u;
          q.push(v);
        }
      }
    }
    int mx = *max_element(d.begin(), d.end());
    return make_pair(mx, src);
  }
  
  void pre_dfs(int u) {
    sz[u] = 1;
    for (auto v : adj[u]) {
      pre_dfs(v);
      sz[u] += sz[v];
    }
  }
  
  void dfs(int u) {
    int big_child = -1;
    for (int i = 0; i < (int)adj[u].size(); ++i) {
      if (big_child == -1 || adj[u][i] > adj[u][big_child]) {
        big_child = i;
      }
    }
    if (big_child != -1) {
      swap(adj[u][0], adj[u][big_child]);
    }
    tin[u] = ++timer;
    et[timer] = u;
    for (auto v : adj[u]) {
      h[v] = h[u] + 1;
      dfs(v);
    }
  }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  n = N;
  for (int i = 0; i < n; ++i) {
    g[i].clear();
    adj[i].clear();
  }
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  pair<int, int> opt = bfs(0);
  for (int i = 0; i < n; ++i) {
    if (par[i] != -1) {
      adj[par[i]].push_back(i);
    }
  }
  pre_dfs(0);
  dfs(0);
  if (opt.first + 1 >= 60) {
    for (int i = 0; i < n; ++i) {
      MessageBoard(i, X >> (h[i] % 60) & 1);
    }
  } else {
    timer = 0;
    for (int i = 0; i < n; ++i) {
      MessageBoard(et[i + 1], X >> (i % 60) & 1);
    }
  }
}

Ioi

#include "Ioi.h"
#include "bits/stdc++.h"

using namespace std;

namespace {
  const int maxn = 1e4 + 4;
  vector<int> g[maxn];
  vector<int> adj[maxn];
  int n;
  int par[maxn];
  int h[maxn];
  int mx[maxn];
  int tin[maxn], timer, et[maxn];
  int sz[maxn];
  
  long long x;
  
  pair<int, int> bfs(int src) {
    queue<int> q;
    vector<int> d(n + 1, -1);
    d[src] = 0;
    par[src] = 0;
    q.push(src);
    memset(par, -1, sizeof(par));
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (d[v] == -1) {
          d[v] = d[u] + 1;
          par[v] = u;
          q.push(v);
        }
      }
    }
    int mx = *max_element(d.begin(), d.end());
    return make_pair(mx, src);
  }
  
  void pre_dfs(int u) {
    sz[u] = 1;
    for (auto v : adj[u]) {
      pre_dfs(v);
      sz[u] += sz[v];
    }
  }
  
  void dfs(int u) {
    int big_child = -1;
    for (int i = 0; i < (int)adj[u].size(); ++i) {
      if (big_child == -1 || adj[u][i] > adj[u][big_child]) {
        big_child = i;
      }
    }
    if (big_child != -1) {
      swap(adj[u][0], adj[u][big_child]);
    }
    tin[u] = ++timer;
    et[timer] = u;
    for (auto v : adj[u]) {
      h[v] = h[u] + 1;
      dfs(v);
    }
  }
  
  void dfs_mx(int u) {
    mx[u] = 1;
    for (auto v : adj[u]) {
      dfs_mx(v);
      mx[u] = max(mx[u], mx[v] + 1);
    }
  }
  
  bool done;
  
  void traverse(int u) {
    if (done) return;
    if (tin[u] == 60) {
      done = 1;
      return;
    }
    for (auto v : adj[u]) {
      if (done) return;
      int nxt = Move(v);
//      if (tin[v] == 60) {
//        done = 1;
//        return;
//      }
      if (nxt) {
        x |= (1ll << (tin[v] - 1));
      }
//      cerr << "Y " << u << " " << v << endl;
      traverse(v);
      if (done) return;
    }
    if (par[u] != -1) {
      Move(par[u]);
    }
  }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  n = N;
  for (int i = 0; i < n; ++i) {
    g[i].clear();
    adj[i].clear();
  }
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  pair<int, int> opt = bfs(0);
  bfs(opt.second);
  for (int i = 0; i < n; ++i) {
    if (par[i] != -1) {
      adj[par[i]].push_back(i);
    }
  }
  timer = 0;
  pre_dfs(0);
  dfs(0);
  if (opt.first + 1 >= 60) {
    if (h[P] >= 59) {
      x = 0;
      vector<int> hehe(60);
      hehe[h[P] % 60] = V;
      for (int i = 1; i < 60; ++i) {
        assert(par[P] != -1);
        hehe[h[par[P]] % 60] = Move(par[P]);
        P = par[P];
      }
      for (int i = 0; i < 60; ++i) {
        if (hehe[i]) x |= (1ll << i);
      }
      return x;
    }
    x = 0;
    while (par[P] != -1) {
      int nxt = Move(par[P]);
      if (par[par[P]] == -1) {
        x = nxt;
      }
      P = par[P];
    }
    dfs_mx(P);
//    cerr << "root " << P << endl;
    for (int i = 0; i < 59; ++i) {
      int v = -1;
      for (auto x : adj[P]) {
        if (v == -1 || mx[x] > mx[v]) v = x;
      }
      if (Move(v)) {
        x |= (1ll << h[v]);
      }
      P = v;
    }
    return x;
  } else {
//    cerr << "HALO" << endl;
    x = V;
    while (par[P] != -1) {
      int nxt = Move(par[P]);
      if (par[par[P]] == -1) {
        x = nxt;
      }
      P = par[P];
    }
//    cerr << "ROOT " << P << endl;
    done = 0;
    traverse(P);
//    cerr << "ans " << x << endl;
    return x;
  }
}

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