Submission #1170080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170080		fryingduc	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	18 ms	2888 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 m;
  int par[maxn];
  int h[maxn];
  int tin[maxn], timer, et[maxn];
  int sz[maxn];
  int mx[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, int prev = -1) {
    sz[u] = 1;
    mx[u] = 1;
    for (auto v : adj[u]) {
      if (v == prev) continue;
      h[v] = h[u] + 1;
      par[v] = u;
      pre_dfs(v, u);
      sz[u] += sz[v];
      mx[u] = max(mx[u], mx[v] + 1);
    }
  }
  
  int find_centroid(int u, int prev, int n) {
    for (auto v : adj[u]) {
      if (v == prev) continue;
      if (sz[v] * 2 > n) return find_centroid(v, u, n);
    }
    return u;
  }
  
  void dfs(int u, int prev = -1) {
//    int big_child = -1;
//    for (int i = 0; i < (int)adj[u].size(); ++i) {
//      if (adj[u][i] == prev) continue;
//      if (big_child == -1 || mx[adj[u][i]] > mx[adj[u][big_child]]) {
//        big_child = i;
//      }
//    }
//    if (big_child != -1) {
//      swap(adj[u][0], adj[u][big_child]);
//    }
    sort(adj[u].begin(), adj[u].end(), [](const int &x, const int &y) -> bool {
//      if (n > 80) {
//        return mx[x] > mx[y];
//      }
//      return sz[x] < sz[y];
      return mx[x] > mx[y];
    });
    tin[u] = ++timer;
    et[timer] = u;
    for (auto v : adj[u]) {
      if (v == prev) continue;
      dfs(v, u);
    }
  }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  n = N, m = M;
  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);
      adj[i].push_back(par[i]);
      h[i] = h[par[i]] + 1;
    }
  }
  int r = max_element(h, h + n) - h;
  h[r] = 0;
  par[r] = -1;
  pre_dfs(r);
  timer = 0;
  dfs(r);
  opt.first = *max_element(h, h + n);
  if (opt.first + 1 >= 60) {
    for (int i = 0; i < n; ++i) {
      MessageBoard(i, X >> (h[i] % 60) & 1);
    }
  } else {
    int c = find_centroid(r, 0, n);
    h[c] = 0;
    par[c] = -1;
    timer = 0;
    pre_dfs(c); dfs(c);
    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 m;
  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, int prev = -1) {
    sz[u] = 1;
    mx[u] = 1;
    for (auto v : adj[u]) {
      if (v == prev) continue;
      h[v] = h[u] + 1;
      par[v] = u;
      pre_dfs(v, u);
      sz[u] += sz[v];
      mx[u] = max(mx[u], mx[v] + 1);
    }
  }
  
  void dfs(int u, int prev = -1) {
//    int big_child = -1;
//    for (int i = 0; i < (int)adj[u].size(); ++i) {
//      if (adj[u][i] == prev) continue;
//      if (big_child == -1 || mx[adj[u][i]] > mx[adj[u][big_child]]) {
//        big_child = i;
//      }
//    }
//    if (big_child != -1) {
//      swap(adj[u][0], adj[u][big_child]);
//    }
    sort(adj[u].begin(), adj[u].end(), [](const int &x, const int &y) -> bool {
//      if (n > 80) {
//        return mx[x] > mx[y];
//      }
//      return sz[x] < sz[y];
      return mx[x] > mx[y];
    });
    tin[u] = ++timer;
    et[timer] = u;
    for (auto v : adj[u]) {
      if (v == prev) continue;
      dfs(v, u);
    }
  }
  
  int find_centroid(int u, int prev, int n) {
    for (auto v : adj[u]) {
      if (v == prev) continue;
      if (sz[v] * 2 > n) return find_centroid(v, u, n);
    }
    return u;
  }
  
  bool done;
  
  void traverse(int u, int prev = -1) {
    if (done) return;
    if (tin[u] == 60) {
      done = 1;
      return;
    }
    for (auto v : adj[u]) {
      if (v == prev) continue;
      if (done) return;
      int nxt = Move(v);
      if (nxt) {
        x |= (1ll << (tin[v] - 1));
      }
      traverse(v, u);
      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, m = M;
  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);
      adj[i].push_back(par[i]);
      h[i] = h[par[i]] + 1;
    }
  }
  int r = max_element(h, h + n) - h;
  h[r] = 0;
  par[r] = -1;
  pre_dfs(r);
  timer = 0;
  dfs(r);
  opt.first = *max_element(h, h + n);
  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 = V;
    while (par[P] != -1) {
      int nxt = Move(par[P]);
      if (par[par[P]] == -1) {
        x = nxt;
      }
      P = par[P];
    }
    for (int i = 0; i < 59; ++i) {
      int v = -1;
      for (auto x : adj[P]) {
        if (x == par[P]) continue;
        if (v == -1 || mx[x] > mx[v]) v = x;
      }
      if (Move(v)) {
        x |= (1ll << h[v]);
      }
      P = v;
    }
    return x;
  } else {
    int c = find_centroid(r, 0, n);
    h[c] = 0;
    par[c] = -1;
    timer = 0;
    pre_dfs(c); dfs(c);
    x = V;
    int cnt = 0;
    while (par[P] != -1) {
      ++cnt;
      int nxt = Move(par[P]);
      if (par[par[P]] == -1) {
        x = nxt;
      }
      P = par[P];
    }
    cerr << "cost " << cnt << endl;
    done = 0;
    traverse(P);
    return x;
  }
}

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