Submission #881780

#	Time	Username	Problem	Language	Result	Execution time	Memory
881780		MattTheNub	Amusement Park (JOI17_amusement_park)	C++17	98 / 100	19 ms	3756 KiB

Joi

#include <bits/stdc++.h>
using namespace std;

template <class T> using v = vector<T>;

#include "Joi.h"

#define all(x) begin(x), end(x)
#define f first
#define s second
using int2 = pair<int, int>;

// communicate 60 bits of information in 120 moves
struct DSU {
  v<int> e;
  DSU(int n) { e = v<int>(n, -1); }

  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
  bool same_set(int a, int b) { return get(a) == get(b); }
  int size(int x) { return -e[get(x)]; }

  bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) {
      return false;
    }
    if (e[x] > e[y]) {
      swap(x, y);
    }
    e[x] += e[y];
    e[y] = x;
    return true;
  }
};

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  v<int> depth(N);
  v<v<int>> adj(N);
  DSU dsu(N);
  for (int i = 0; i < M; i++) {
    if (dsu.unite(A[i], B[i])) {
      adj[A[i]].push_back(B[i]);
      adj[B[i]].push_back(A[i]);
    }
  }

  auto dfs = [&](int u, int p, auto &&dfs) -> void {
    for (int v : adj[u]) {
      if (v != p) {
        depth[v] = depth[u] + 1;
        dfs(v, u, dfs);
      }
    }
  };
  dfs(0, -1, dfs);
  int U = max_element(all(depth)) - depth.begin();
  depth.assign(N, 0);
  dfs(U, -1, dfs);
  int V = max_element(all(depth)) - depth.begin();
  int d = depth[V];
  if (d >= 60) {
    for (int i = 0; i < N; i++) {
      MessageBoard(i, (X >> (depth[i] % 60)) & 1);
    }
  } else {
    int r = find(all(depth), d / 2) - depth.begin();
    v<int> len(N);
    auto dfs_len = [&](int u, int p, auto &&dfs_len) -> void {
      for (int v : adj[u]) {
        if (v != p) {
          dfs_len(v, u, dfs_len);
          len[u] = max(len[u], len[v] + 1);
        }
      }
    };
    dfs_len(U, -1, dfs_len);

    v<int> num(N, -1);
    int cnt = 0;
    auto dfs = [&](int u, int p, auto &&dfs) -> void {
      if (cnt < 60) {
        num[u] = cnt++;
      }
      v<int2> ch;
      for (int v : adj[u]) {
        if (v != p) {
          ch.push_back({len[v], v});
        }
      }

      sort(all(ch), greater<int2>());
      for (auto v : ch) {
        dfs(v.s, u, dfs);
      }
    };

    dfs(r, -1, dfs);

    for (int i = 0; i < N; i++) {
      if (num[i] != -1) {
        MessageBoard(i, (X >> num[i]) & 1);
      } else {
        MessageBoard(i, 0);
      }
    }
  }
}

Ioi

#include "Ioi.h"

#include <bits/stdc++.h>
using namespace std;

template <class T> using v = vector<T>;
#define all(x) begin(x), end(x)
using int2 = pair<int, int>;
using ll = long long;
#define f first
#define s second

// communicate 60 bits of information in 120 moves
struct DSU {
  v<int> e;
  DSU(int n) { e = v<int>(n, -1); }

  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
  bool same_set(int a, int b) { return get(a) == get(b); }
  int size(int x) { return -e[get(x)]; }

  bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) {
      return false;
    }
    if (e[x] > e[y]) {
      swap(x, y);
    }
    e[x] += e[y];
    e[y] = x;
    return true;
  }
};

long long Ioi(int N, int M, int A[], int B[], int P, int VI, int T) {
  v<int> depth(N);
  v<v<int>> adj(N);
  DSU dsu(N);
  for (int i = 0; i < M; i++) {
    if (dsu.unite(A[i], B[i])) {
      adj[A[i]].push_back(B[i]);
      adj[B[i]].push_back(A[i]);
    }
  }

  v<int> up(N, -1);
  auto dfs = [&](int u, int p, auto &&dfs) -> void {
    up[u] = p;
    for (int v : adj[u]) {
      if (v != p) {
        depth[v] = depth[u] + 1;
        dfs(v, u, dfs);
      }
    }
  };
  dfs(0, -1, dfs);
  int U = max_element(all(depth)) - depth.begin();
  depth.assign(N, 0);
  dfs(U, -1, dfs);
  int V = max_element(all(depth)) - depth.begin();
  int d = depth[V];
  if (d >= 60) {
    if (depth[P] >= 60) {
      cerr << "case 1\n";
      ll ans = 0;
      for (int _ = 0; _ < 60; _++) {
        ans ^= (ll)VI << (depth[P] % 60);
        P = up[P];
        VI = Move(P);
      }
      return ans;
    } else {
      cerr << "case 2\n";
      while (P != U) {
        P = up[P];
        VI = Move(P);
      }
      v<int> down(N, -1);
      auto path = [&](int u, int p, auto &&path) -> void {
        for (int v : adj[u]) {
          if (v != p) {
            path(v, u, path);
            if (v == V) {
              down[u] = v;
            } else if (down[v] != -1) {
              down[u] = v;
            }
          }
        }
      };
      path(P, -1, path);
      ll ans = 0;
      for (int i = 0; i < 60; i++) {
        ans ^= (ll)VI << i;
        P = down[P];
        VI = Move(P);
      }
      return ans;
    }
  } else {
    cerr << "case 3\n";
    int r = find(all(depth), d / 2) - depth.begin();
    v<int> len(N);
    auto dfs_len = [&](int u, int p, auto &&dfs_len) -> void {
      for (int v : adj[u]) {
        if (v != p) {
          dfs_len(v, u, dfs_len);
          len[u] = max(len[u], len[v] + 1);
        }
      }
    };
    dfs_len(U, -1, dfs_len);

    v<int> num(N, -1);
    int cnt = 0;
    auto dfs = [&](int u, int p, auto &&dfs) -> void {
      up[u] = p;
      if (cnt < 60) {
        num[u] = cnt++;
      }
      v<int2> ch;
      for (int v : adj[u]) {
        if (v != p) {
          ch.push_back({len[v], v});
        }
      }

      sort(all(ch), greater<int2>());
      for (auto v : ch) {
        dfs(v.s, u, dfs);
      }
    };

    dfs(r, -1, dfs);
    while (P != r) {
      P = up[P];
      VI = Move(P);
    }
    cnt = 0;
    ll ans = 0;
    auto trav = [&](int u, int p, auto &&trav) -> void {
      cnt++;
      ans ^= (ll)VI << num[u];
      v<int2> ch;
      for (int v : adj[u]) {
        if (v != p) {
          ch.push_back({len[v], v});
        }
      }

      sort(all(ch));
      for (auto v : ch) {
        if (num[v.s] != -1) {
          VI = Move(v.s);
          trav(v.s, u, trav);
          if (cnt < 60) {
            VI = Move(u);
          }
        }
      }
    };
    trav(r, -1, trav);

    return ans;
  }
}

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