oj.uz

Submission #341588

# Submission time Handle Problem Language Result Execution time Memory
341588 2020-12-30T06:45:43 Z KoD Amusement Park (JOI17_amusement_park) C++17
0 / 100
 33 ms 6276 KB 
#include "Joi.h"
#include <vector>
#include <queue>
#include <array>

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;
  }
}

#include "Ioi.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;

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);
  for (const auto u: groups[group_id[P]]) {
    same_group[u] = true;
  }
  written[P] = T;
  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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 740 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 5956 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 868 KB Output is correct
2 Incorrect 1 ms 960 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6056 KB Output is correct
2 Incorrect 33 ms 6276 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6036 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -