Submission #824678

#	Time	Username	Problem	Language	Result	Execution time	Memory
824678		erray	Split the Attractions (IOI19_split)	C++17	100 / 100	183 ms	35320 KiB

split

#include "split.h"

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi19/d1/debug.h"
#else 
  #define debug(...) void(37)
#endif


struct DSU {
  vector<int> link;
  DSU(int n) {
    link.resize(n);
    iota(link.begin(), link.end(), 0);
  }
  int get(int v) {
    return link[v] = (v == link[v] ? v : get(link[v]));
  }
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) {
      return false;
    }
    link[y] = x;
    return true;
  }
};
  
vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
  array<array<int, 2>, 3> ord{};
  ord[0] = {A, 1};
  ord[1] = {B, 2};
  ord[2] = {C, 3};
  sort(ord.begin(), ord.end());
  vector<vector<int>> g(N);
  int M = int(P.size());
  for (int i = 0; i < M; ++i) {
    g[P[i]].push_back(Q[i]);
    g[Q[i]].push_back(P[i]);
  }
  auto Build = [&](int root, vector<vector<int>>& dfs_g) {
    vector<int> size(N, 1);
    vector<bool> vis(N);
    vector<int> from(N, -1);
    vector<vector<int>> tree(N);
    function<void(int)> Dfs = [&](int v) {
      vis[v] = true;
      for (auto u : dfs_g[v]) {
        if (!vis[u]) {
          from[u] = (from[v] == -1 ? u : from[v]);
          Dfs(u);
          tree[v].push_back(u);
          tree[u].push_back(v);
          size[v] += size[u];
        }
      }
    };
    Dfs(root);
    return make_tuple(tree, size, from);
  }; 
  auto[tree, size, from] = Build(0, g);
  debug(tree, size, from);
  int lower = N / 3;
  //int lower = ord[0][0];
  int upper = N - lower;
  int root = 0;
  while (true) {
    int go = -1;
    for (auto u : tree[root]) {
      if (size[u] > upper) {
        go = u;
      }
    }
    if (go == -1) {
      break;
    }
    size[root] = N - size[go];
    size[go] = N;
    root = go;
  }
  tie(tree, size, from) = Build(root, tree);
  debug(root, size, from);
  for (auto u : tree[root]) {
    assert(size[u] <= upper);
  }
  DSU group(N);
  for (int i = 0; i < M; ++i) {
    if (from[P[i]] != -1 && from[Q[i]] != -1) {
      group.unite(from[P[i]], from[Q[i]]);
    }
  }
  vector<int> tot(N);
  for (auto u : tree[root]) {
    tot[group.get(u)] += size[u];
  }
  int use = int(max_element(tot.begin(), tot.end()) - tot.begin());
  debug(use);
  if (tot[use] < ord[0][0]) {
    return vector<int>(N, 0);
  }
  for (auto u : tree[root]) {
    if (size[u] >= lower) {
      use = u;
    }
  }
  vector<bool> take(N);
  vector<vector<int>> comp_g(N);
  for (int i = 0; i < M; ++i) {
    int x = from[P[i]], y = from[Q[i]];
    if (x != -1 && y != -1) {
      comp_g[x].push_back(y);
      comp_g[y].push_back(x);
    }
  }
  int taken = 0;
  function<void(int)> Expand = [&](int v) {
    take[v] = true;
    taken += size[v];
    for (auto u : comp_g[v]) {
      if (!take[u] && taken < ord[0][0]) {
        Expand(u);
      }
    }
  };
  Expand(use);
  assert(taken >= ord[0][0]);
  debug(take);
  if (taken >= ord[1][0]) {
    swap(ord[0], ord[1]);
  }
  vector<int> ans(N, 3);
  function<void(int, int&, int)> Set = [&](int v, int& left, int id) {
    --left;
    ans[v] = id;
    for (auto u : g[v]) {
      if (ans[u] == 3 && left > 0) {
        Set(u, left, id);
      }
    }
  };
  int small = ord[0][0];
  for (int i = 0; i < N; ++i) {
    if (from[i] == -1 || !take[from[i]]) {
      ans[i] = 2;
    }
  }
  Set(use, small, 1);
  assert(small <= 0);
  for (int i = 0; i < N; ++i) {
    if (ans[i] != 1) {
      ans[i] = 3;
    }
  }
  int middle = ord[1][0];
  Set(root, middle, 2);
  assert(middle == 0);
  for (int i = 0; i < N; ++i) {
    ans[i] = ord[ans[i] - 1][1];
  }
  return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36