Submission #652324

#	Time	Username	Problem	Language	Result	Execution time	Memory
652324		evenvalue	Split the Attractions (IOI19_split)	C++17	22 / 100	671 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

vector<int> reject(const int n) {
  vector<int> v(n);
  return v;
}

vector<int> find_split(int n, int A, int B, int C, vector<int> P, vector<int> Q) {
  vector<pair<int, int>> v = {{A, 1}, {B, 2}, {C, 3}};
  sort(v.begin(), v.end());
  A = v[0].first, B = v[1].first, C = v[2].first;

  const int m = P.size();

  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    const int x = P[i], y = Q[i];
    g[x].push_back(y);
    g[y].push_back(x);
  }

  vector<int> ss(n, 1);
  int U = -1, V = -1;
  function<int(int, int)> dfs = [&](const int x, const int p) {
    for (const int y : g[x]) {
      if (y == p) continue;
      ss[x] += dfs(y, x);
    }
    if (ss[x] >= A and n - ss[x] >= B) {
      U = x;
      V = p;
    } else if (ss[x] >= B and n - ss[x] >= A) {
      U = p;
      V = x;
    }
    return ss[x];
  };

  dfs(0, -1);

  if (U == -1) return reject(n);

  vector<int> assign(n, 3);

  function<void(int, int, int, int&)> dfs2 = [&](const int x, const int p, const int i, int &sz) {
    if (sz == 0) return;
    sz--;
    assign[x] = i;
    for (const int y : g[x]) {
      if (y == p) continue;
      dfs2(y, x, i, sz);
    }
  };

  dfs2(U, V, v[0].second, A);
  dfs2(V, U, v[1].second, B);

  return assign;
}

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