Submission #1316258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316258		Kaguya	Split the Attractions (IOI19_split)	C++20	0 / 100	50 ms	14628 KiB

split

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

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  int m = (int)p.size();
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    g[p[i]].push_back(q[i]);
    g[q[i]].push_back(p[i]);
  }
  vector<int> sz(n, 0);
  vector<int> pr(n, -1);
  vector<int> low(n, -1), tin(n, -1);
  int tt = 0;
  function<void(int, int)> dfs = [&](int v, int pred) {
    sz[v] = 1;
    pr[v] = pred;
    tin[v] = low[v] = tt++;
    for (int to : g[v]) {
      if (to == pred) {
        continue;
      }
      if (tin[to] != -1) {
        low[v] = min(low[v], tin[to]);
      } else {
        dfs(to, v);
        sz[v] += sz[to];
        low[v] = min(low[v], low[to]);
      }
    }
  };
  dfs(0, -1);
  vector<pair<int, int>> ve = {{a, 1}, {b, 2}, {c, 3}};
  sort(ve.begin(), ve.end());
  vector<int> ans(n, 0);
  auto color = [&](int from, int cnt, int col, vector<bool>& was) -> void {
    queue<int> que;
    que.push(from);
    was[from] = true;
    que.push(from);
    ans[from] = col;
    int paint = 1;
    while (!que.empty() && paint < cnt) {
      int v = que.front();
      que.pop();
      for (int to : g[v]) {
        if (was[to]) {
          continue;
        }
        que.push(to);
        was[to] = true;
        if (paint < cnt) {
          paint++;
          ans[to] = col;
        }
        if (paint == col) {
          return;
        }
      }
    }
  };
  int cent = -1;
  for (int i = 0; i < n; i++) {
    if ((n - sz[i]) > n / 2) {
      continue;
    }
    bool ok = true;
    for (int to : g[i]) {
      if (pr[to] == i && sz[to] > n / 2) {
        ok = false;
        break;
      }
    }
    if (ok) {
      cent = i;
      break;
    }
  }
  vector<int> cand;
  int sum = n - sz[cent];
  for (int to : g[cent]) {
    if (pr[to] != cent) {
      continue;
    }
    if (sz[to] >= ve[0].first) {
      vector<bool> was(n, false);
      was[cent] = true;
      color(to, ve[0].first, ve[0].second, was);
      was[cent] = false;
      for (int i = 0; i < n; i++) {
        if (ans[i] != 0) {
          was[i] = true;
        }
      }
      color(cent, ve[1].first, ve[1].second, was);
      for (int i = 0; i < n; i++) {
        if (ans[i] == 0) {
          ans[i] = ve.back().second;
        }
      }
      return ans;
    }
    if (low[to] < tin[cent]) {
      cand.push_back(to);
      sum += sz[to];
    }
  }
  if (sum >= ve[0].first) {
    vector<bool> is_a(n, false);
    vector<bool> sel(n, false);
    int cur = n - sz[cent];
    vector<int> has;
    for (int v : cand) {
      if (cur < ve[0].first) {
        cur += sz[v];
        has.push_back(v);
        sel[v] = true;
      }
    }
    vector<bool> was(n, false);
    was[cent] = true;
    for (int to : g[cent]) {
      if (pr[to] == cent && !sel[to]) {
        was[to] = true;
      }
    }
    int start = (pr[cent] != -1 ? pr[cent] : has[0]);
    color(start, ve[0].first, ve[0].second, was);
    vector<bool> was2(n, false);
    for (int i = 0; i < n; i++) {
      if (ans[i] != 0) {
        was2[i] = true;
      }
    }
    color(cent, ve[1].first, ve[1].second, was2);
    for (int i = 0; i < n; i++) {
      if (ans[i] == 0) {
        ans[i] = ve.back().second;
      }
    }
    return ans;
  }
  return ans;
}

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