oj.uz

Submission #341591

# Submission time Handle Problem Language Result Execution time Memory
341591 2020-12-30T06:57:40 Z KoD Amusement Park (JOI17_amusement_park) C++17
100 / 100
 280 ms 9968 KB 
#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;
  }
}

#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1004 KB Output is correct
2 Correct 2 ms 872 KB Output is correct
3 Correct 2 ms 908 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 744 KB Output is correct
6 Correct 2 ms 744 KB Output is correct
7 Correct 2 ms 1136 KB Output is correct
8 Correct 2 ms 1008 KB Output is correct
9 Correct 2 ms 948 KB Output is correct
10 Correct 2 ms 936 KB Output is correct
11 Correct 5 ms 1076 KB Output is correct
12 Correct 2 ms 956 KB Output is correct
13 Correct 3 ms 880 KB Output is correct
14 Correct 2 ms 880 KB Output is correct
15 Correct 2 ms 880 KB Output is correct
16 Correct 2 ms 904 KB Output is correct
17 Correct 2 ms 880 KB Output is correct
18 Correct 2 ms 880 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5956 KB Output is correct
2 Correct 33 ms 6424 KB Output is correct
3 Correct 33 ms 6276 KB Output is correct
4 Correct 28 ms 5264 KB Output is correct
5 Correct 19 ms 5132 KB Output is correct
6 Correct 24 ms 5132 KB Output is correct
7 Correct 24 ms 5132 KB Output is correct
8 Correct 24 ms 5388 KB Output is correct
9 Correct 24 ms 5516 KB Output is correct
10 Correct 258 ms 9608 KB Output is correct
11 Correct 255 ms 9608 KB Output is correct
12 Correct 23 ms 4816 KB Output is correct
13 Correct 27 ms 5024 KB Output is correct
14 Correct 32 ms 5132 KB Output is correct
15 Correct 26 ms 5196 KB Output is correct
16 Correct 26 ms 4876 KB Output is correct
17 Correct 27 ms 5260 KB Output is correct
18 Correct 31 ms 5260 KB Output is correct
19 Correct 28 ms 5132 KB Output is correct
20 Correct 16 ms 5352 KB Output is correct
21 Correct 16 ms 5132 KB Output is correct
22 Correct 20 ms 4988 KB Output is correct
23 Correct 20 ms 5172 KB Output is correct
24 Correct 23 ms 5004 KB Output is correct
25 Correct 20 ms 5032 KB Output is correct
26 Correct 20 ms 5132 KB Output is correct
27 Correct 20 ms 5132 KB Output is correct
28 Correct 20 ms 5240 KB Output is correct
29 Correct 19 ms 4696 KB Output is correct
30 Correct 19 ms 4908 KB Output is correct
31 Correct 2 ms 932 KB Output is correct
32 Correct 2 ms 940 KB Output is correct
33 Correct 2 ms 1236 KB Output is correct
34 Correct 2 ms 1112 KB Output is correct
35 Correct 2 ms 872 KB Output is correct
36 Correct 2 ms 744 KB Output is correct
37 Correct 2 ms 872 KB Output is correct
38 Correct 2 ms 956 KB Output is correct
39 Correct 2 ms 956 KB Output is correct
40 Correct 2 ms 744 KB Output is correct
41 Correct 2 ms 944 KB Output is correct
42 Correct 2 ms 872 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 948 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 2 ms 1032 KB Output is correct
4 Correct 4 ms 1600 KB Output is correct
5 Correct 4 ms 1556 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct
7 Correct 4 ms 1684 KB Output is correct
8 Correct 3 ms 1556 KB Output is correct
9 Correct 17 ms 6012 KB Output is correct
10 Correct 16 ms 6012 KB Output is correct
11 Correct 17 ms 6012 KB Output is correct
12 Correct 2 ms 744 KB Output is correct
13 Correct 2 ms 952 KB Output is correct
14 Correct 2 ms 872 KB Output is correct
15 Correct 2 ms 956 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5956 KB Output is correct
2 Correct 36 ms 6084 KB Output is correct
3 Correct 32 ms 6284 KB Output is correct
4 Correct 39 ms 5288 KB Output is correct
5 Correct 25 ms 5564 KB Output is correct
6 Correct 29 ms 5616 KB Output is correct
7 Correct 24 ms 5404 KB Output is correct
8 Correct 23 ms 5264 KB Output is correct
9 Correct 23 ms 5276 KB Output is correct
10 Correct 254 ms 9968 KB Output is correct
11 Correct 280 ms 9752 KB Output is correct
12 Correct 23 ms 4740 KB Output is correct
13 Correct 25 ms 4996 KB Output is correct
14 Correct 24 ms 4752 KB Output is correct
15 Correct 26 ms 5020 KB Output is correct
16 Correct 27 ms 5056 KB Output is correct
17 Correct 30 ms 5308 KB Output is correct
18 Correct 28 ms 5524 KB Output is correct
19 Correct 31 ms 5276 KB Output is correct
20 Correct 17 ms 5276 KB Output is correct
21 Correct 17 ms 5244 KB Output is correct
22 Correct 25 ms 5020 KB Output is correct
23 Correct 19 ms 4892 KB Output is correct
24 Correct 19 ms 5020 KB Output is correct
25 Correct 19 ms 5148 KB Output is correct
26 Correct 19 ms 5148 KB Output is correct
27 Correct 23 ms 5148 KB Output is correct
28 Correct 19 ms 5020 KB Output is correct
29 Correct 19 ms 4800 KB Output is correct
30 Correct 19 ms 4880 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5956 KB Output is correct
2 Correct 37 ms 6436 KB Output is correct
3 Correct 33 ms 6276 KB Output is correct
4 Correct 32 ms 5276 KB Output is correct
5 Correct 19 ms 6060 KB Output is correct
6 Correct 23 ms 5276 KB Output is correct
7 Correct 24 ms 5276 KB Output is correct
8 Correct 26 ms 5512 KB Output is correct
9 Correct 24 ms 5148 KB Output is correct
10 Correct 258 ms 9820 KB Output is correct
11 Correct 256 ms 9764 KB Output is correct
12 Correct 31 ms 4868 KB Output is correct
13 Correct 28 ms 5012 KB Output is correct
14 Correct 23 ms 4752 KB Output is correct
15 Correct 28 ms 5224 KB Output is correct
16 Correct 27 ms 5148 KB Output is correct
17 Correct 27 ms 5148 KB Output is correct
18 Correct 27 ms 5348 KB Output is correct
19 Correct 27 ms 5340 KB Output is correct
20 Correct 20 ms 5344 KB Output is correct
21 Correct 17 ms 5148 KB Output is correct
22 Correct 20 ms 5032 KB Output is correct
23 Correct 20 ms 5196 KB Output is correct
24 Correct 20 ms 5020 KB Output is correct
25 Correct 24 ms 5044 KB Output is correct
26 Correct 25 ms 4892 KB Output is correct
27 Correct 26 ms 5328 KB Output is correct
28 Correct 20 ms 5276 KB Output is correct
29 Correct 22 ms 4876 KB Output is correct
30 Correct 22 ms 5008 KB Output is correct
31 Correct 2 ms 744 KB Output is correct
32 Correct 2 ms 940 KB Output is correct
33 Correct 2 ms 1008 KB Output is correct
34 Correct 2 ms 884 KB Output is correct
35 Correct 2 ms 744 KB Output is correct
36 Correct 1 ms 952 KB Output is correct
37 Correct 2 ms 872 KB Output is correct
38 Correct 1 ms 788 KB Output is correct
39 Correct 2 ms 964 KB Output is correct
40 Correct 1 ms 744 KB Output is correct
41 Correct 2 ms 744 KB Output is correct
42 Correct 1 ms 744 KB Output is correct