Submission #1316263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316263		Kaguya	Split the Attractions (IOI19_split)	C++20	Compilation error	0 ms	0 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, bool tree_only) -> void {
    queue<int> que;
    que.push(from);
    was[from] = true;
    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;
        }
        if (tree_only && pr[to] != v && pr[v] != to) {
          continue;
        }
        que.push(to);
        was[to] = true;
        if (paint < cnt) {
          paint++;
          ans[to] = col;
        }
        if (paint == cnt) {
          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);
      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;
    }
    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;
  }
  for (int i = 0; i < n; i++) {
    ans[i] = 0;
  }
  return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:90:12: error: no match for call to '(find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, int, std::vector<bool>&, bool)>) (int&, int&, int&, std::vector<bool>&)'
   90 |       color(to, ve[0].first, ve[0].second, was);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:36:16: note: candidate: 'find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, int, std::vector<bool>&, bool)>'
   36 |   auto color = [&](int from, int cnt, int col, vector<bool>& was, bool tree_only) -> void {
      |                ^
split.cpp:36:16: note:   candidate expects 5 arguments, 4 provided
split.cpp:97:12: error: no match for call to '(find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, int, std::vector<bool>&, bool)>) (int&, int&, int&, std::vector<bool>&)'
   97 |       color(cent, ve[1].first, ve[1].second, was2);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:36:16: note: candidate: 'find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, int, std::vector<bool>&, bool)>'
   36 |   auto color = [&](int from, int cnt, int col, vector<bool>& was, bool tree_only) -> void {
      |                ^
split.cpp:36:16: note:   candidate expects 5 arguments, 4 provided
split.cpp:130:10: error: no match for call to '(find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, int, std::vector<bool>&, bool)>) (int&, int&, int&, std::vector<bool>&)'
  130 |     color(start, ve[0].first, ve[0].second, was);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:36:16: note: candidate: 'find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, int, std::vector<bool>&, bool)>'
   36 |   auto color = [&](int from, int cnt, int col, vector<bool>& was, bool tree_only) -> void {
      |                ^
split.cpp:36:16: note:   candidate expects 5 arguments, 4 provided
split.cpp:137:10: error: no match for call to '(find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, int, std::vector<bool>&, bool)>) (int&, int&, int&, std::vector<bool>&)'
  137 |     color(cent, ve[1].first, ve[1].second, was2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:36:16: note: candidate: 'find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, int, std::vector<bool>&, bool)>'
   36 |   auto color = [&](int from, int cnt, int col, vector<bool>& was, bool tree_only) -> void {
      |                ^
split.cpp:36:16: note:   candidate expects 5 arguments, 4 provided