Submission #341591

#	Time	Username	Problem	Language	Result	Execution time	Memory
341591		KoD	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	280 ms	9968 KiB

Joi

#include "Joi.h"
#include <vector>
#include <queue>
#include <array>
#include <iostream>

namespace {

template <class T>
using Vec = std::vector<T>;

Vec<Vec<int>> graph;

Vec<bool> seen;
Vec<Vec<int>> tree;
Vec<int> order;
Vec<int> parent;

Vec<int> group_id;
Vec<int> label;
Vec<Vec<int>> groups;

void construct(const int u, const int p) {
  order.push_back(u);
  parent[u] = p;
  for (const auto v: graph[u]) {
    if (!seen[v]) {
      seen[v] = true;
      tree[u].push_back(v);
      tree[v].push_back(u);
      construct(v, u);
    }
  }
}
};

void Joi(int N, int M, int A[], int B[], long long X, int T) {
  graph.resize(N);
  for (int i = 0; i < M; ++i) {
    graph[A[i]].push_back(B[i]);
    graph[B[i]].push_back(A[i]);
  }

  seen.resize(N);
  tree.resize(N);
  parent.resize(N);
  seen[0] = true;
  construct(0, -1);

  group_id.resize(N, -1);
  label.resize(N, -1);

  int id = 0;
  for (const auto src: order) {
    if (group_id[src] != -1) {
      continue;
    }
    Vec<int> newg;
    {
      std::queue<int> que;
      que.push(src);
      while (!que.empty() && newg.size() < 60) {
        const auto u = que.front();
        que.pop();
        newg.push_back(u);
        for (const auto v: tree[u]) {
          if (v != parent[u]) {
            que.push(v);
          }
        }
      }
    }
    for (const auto u: newg) {
      group_id[u] = id;
    }
    Vec<int> oldg;
    if (newg.size() < 60) {
      const int g = group_id[parent[src]];
      std::queue<std::pair<int, int>> que;
      que.emplace(parent[src], src);
      while (newg.size() + oldg.size() < 60) {
        const auto u = que.front().first;
        const auto p = que.front().second;
        que.pop();
        oldg.push_back(u);
        for (const auto v: tree[u]) {
          if (v != p && group_id[v] == g) {
            que.emplace(v, u);
          }
        }
      }
    }
    std::array<bool, 60> used{};
    for (const auto u: oldg) {
      used[label[u]] = true;
    }
    {
      int index = 0;
      for (const auto u: newg) {
        while (used[index]) {
          index += 1;
        }
        label[u] = index;
        MessageBoard(u, X >> index & 1);
        used[index] = true;
      }
    }
    groups.push_back({ });
    for (const auto u: oldg) {
      groups.back().push_back(u);
    }
    for (const auto u: newg) {
      groups.back().push_back(u);
    }
    id += 1;
  }
}

Ioi

#include "Ioi.h"
#include <vector>
#include <queue>
#include <array>
#include <iostream>
#include <cassert>

namespace {

template <class T>
using Vec = std::vector<T>;

Vec<Vec<int>> graph;

Vec<bool> seen;
Vec<Vec<int>> tree;
Vec<int> order;
Vec<int> parent;

Vec<int> group_id;
Vec<int> label;
Vec<Vec<int>> groups;

Vec<bool> same_group;
Vec<bool> written;

void construct(const int u, const int p) {
  order.push_back(u);
  parent[u] = p;
  for (const auto v: graph[u]) {
    if (!seen[v]) {
      seen[v] = true;
      tree[u].push_back(v);
      tree[v].push_back(u);
      construct(v, u);
    }
  }
}
};

void search(const int u, const int p) {
  for (const auto v: tree[u]) {
    if (same_group[v] && v != p) {
      written[v] = Move(v);
      search(v, u);
    }
  }
  if (p != -1) {
    Move(p);
  }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  graph.resize(N);
  for (int i = 0; i < M; ++i) {
    graph[A[i]].push_back(B[i]);
    graph[B[i]].push_back(A[i]);
  }

  seen.resize(N);
  tree.resize(N);
  parent.resize(N);
  seen[0] = true;
  construct(0, -1);

  group_id.resize(N, -1);
  label.resize(N, -1);

  int id = 0;
  for (const auto src: order) {
    if (group_id[src] != -1) {
      continue;
    }
    Vec<int> newg;
    {
      std::queue<int> que;
      que.push(src);
      while (!que.empty() && newg.size() < 60) {
        const auto u = que.front();
        que.pop();
        newg.push_back(u);
        for (const auto v: tree[u]) {
          if (v != parent[u]) {
            que.push(v);
          }
        }
      }
    }
    for (const auto u: newg) {
      group_id[u] = id;
    }
    Vec<int> oldg;
    if (newg.size() < 60) {
      const int g = group_id[parent[src]];
      std::queue<std::pair<int, int>> que;
      que.emplace(parent[src], src);
      while (newg.size() + oldg.size() < 60) {
        const auto u = que.front().first;
        const auto p = que.front().second;
        que.pop();
        oldg.push_back(u);
        for (const auto v: tree[u]) {
          if (v != p && group_id[v] == g) {
            que.emplace(v, u);
          }
        }
      }
    }
    std::array<bool, 60> used{};
    for (const auto u: oldg) {
      used[label[u]] = true;
    }
    {
      int index = 0;
      for (const auto u: newg) {
        while (used[index]) {
          index += 1;
        }
        label[u] = index;
        used[index] = true;
      }
    }
    groups.push_back({ });
    for (const auto u: oldg) {
      groups.back().push_back(u);
    }
    for (const auto u: newg) {
      groups.back().push_back(u);
    }
    id += 1;
  }

  same_group.resize(N);
  written.resize(N, -1);
  for (const auto u: groups[group_id[P]]) {
    same_group[u] = true;
  }
  written[P] = V;
  search(P, -1);
  long long ret = 0;
  for (const auto u: groups[group_id[P]]) {
    if (written[u]) {
      ret |= (1ll << label[u]);
    }
  }
  return ret;
}

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