제출 #1049587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049587		Halit	Split the Attractions (IOI19_split)	C++17	100 / 100	63 ms	25484 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) { 
  // 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, n+1), 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;
  }
  auto best_bad_subtree = [&]() {
    int res = 0;
    for (int i = 1;i < n; ++i) {
      if (size[i] <= b + c) {
        continue;
      }
      if (size[i] < size[res]) {
        res = i;
      }
    }
    return res;
  };
  std::vector<bool> can(n, true);
  int best_bad = best_bad_subtree();
  int cur_size = size[best_bad];  
  for (int v : tree[best_bad]) {
    if (low[v] < depth[best_bad]) {
      can[v] = false;
      cur_size -= size[v];
    }
    if (cur_size >= a && cur_size <= b + c) {
      good = best_bad;
      break;
    }
  }
  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]) {
        if (can[v]) 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 : adj[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);
}

컴파일 시 표준 에러 (stderr) 메시지

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

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