Submission #1049574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049574		Halit	Split the Attractions (IOI19_split)	C++17	40 / 100	55 ms	25432 KiB

split

#include "split.h"
#include <bits/stdc++.h>

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) { 
  // dfs-tree
  // find good subtree
  // if it doesn't exist find best bad subtree 
  // find removable subtrees of bb-subtree and remove them greedyly
  // if the resulting subtree's size >= A and <= A+C solved
  std::vector<int> colors = {0, 1, 2};
  {
    if (a <= b && b <= c) colors = {1, 2, 3};
    else if (a <= c && c <= b) colors = {1, 3, 2};
    else if (b <= a && a <= c) colors = {2, 1, 3};
    else if (b <= c && c <= a) colors = {2, 3, 1};
    else if (c <= b && b <= a) colors = {3, 2, 1};
    else if (c <= a && a <= b) colors = {3, 1, 2};
    int min = std::min({a, b, c});
    int max = std::max({a, b, c});
    int mid = n - min - max;
    a = min, b = mid, c = max;
  }
  std::vector<std::vector<int>> adj(n);
  for (int i = 0;i < p.size(); ++i) {
    adj[p[i]].push_back(q[i]);
    adj[q[i]].push_back(p[i]);
  }
  std::vector<std::vector<int>> tree(n);
  std::vector<int> depth(n, -1), low(n), size(n);
  std::function<void(int, int, int)> dfs_tree = [&](int u, int par, int d) -> void {
    depth[u] = low[u] = d;
    size[u] = 1;
    for (int v : adj[u]) {
      if (v == par) {
        continue;
      }
      low[u] = std::min(low[u], low[v]);
      if (depth[v] != -1) {
        low[u] = std::min(low[u], depth[v]);
        continue;
      }
      dfs_tree(v, u, d+1);
      size[u] += size[v];
      tree[u].push_back(v);
    }
  };
  dfs_tree(0, -1, 0);
  auto good_subtree = [&]() {
    int res = -1;
    for (int i = 0;i < n; ++i) {
      if (size[i] >= a && size[i] <= b + c) {
        res = i;
      }
    }
    return res;
  };
  std::vector<int> ans(n, -1);
  int good = good_subtree();
  if (good != -1) {
    std::queue<int> q;
    int type = size[good] >= b;
    q.push(good);
    while (q.size() && (type ? b : a)) {
      int u = q.front();
      q.pop();
      ans[u] = colors[type];
      (type ? b : a) -= 1;
      for (int v : tree[u]) {
        q.push(v);
      }
    }
    std::queue<int> q2;
    q2.push(0);
    while (q2.size() && (type ? a : b)) {
      int u = q2.front();
      q2.pop();
      if (ans[u] != -1) {
        continue;
      }
      ans[u] = colors[type^1];
      (type ? a : b) -= 1;
      for (int v : tree[u]) {
        q2.push(v);
      }
    }
    for (int i = 0;i < n; ++i) {
      if (ans[i] == -1) {
        ans[i] = colors[2];
      }
    }
    return ans;
  }
  return std::vector<int>(n, 0);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (int i = 0;i < p.size(); ++i) {
      |                  ~~^~~~~~~~~~

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