Submission #899513

#	Time	Username	Problem	Language	Result	Execution time	Memory
899513		rxlfd314	Split the Attractions (IOI19_split)	C++17	40 / 100	78 ms	16504 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

vt<int> find_split(int N, int X, int Y, int Z, vt<int> P, vt<int> Q) {
  ari2 A = {X, 1}, B = {Y, 2}, C = {Z, 3};
  if (B > C)
    swap(B, C);
  if (A > B)
    swap(A, B);
  if (B > C)
    swap(B, C);
  vt<int> adj[N];
  bool sub1 = true;
  FOR(i, 0, size(P)-1) {
    adj[P[i]].push_back(Q[i]);
    adj[Q[i]].push_back(P[i]);
    sub1 &= size(adj[P[i]]) < 3 && size(adj[Q[i]]) < 3;
  }
  if (sub1) {
    int s = 0;
    FOR(i, 0, N-1)
      if (size(adj[i]) == 1)
        s = i;
    int cur = s, p = s;
    vt<int> ans(N, C[1]);
    while (A[0]--) {
      ans[cur] = A[1];
      for (int i : adj[cur])
        if (i != p) {
          p = cur;
          cur = i;
          break;
        }
    }
    while (B[0]--) {
      ans[cur] = B[1];
      for (int i : adj[cur])
        if (i != p) {
          p = cur;
          cur = i;
          break;
        }
    }
    return ans;
  }
  if (size(P) == N-1) {
    #ifdef DEBUG
    cout << "LOL\n";
    #endif
    int szs[N];
    function<int(int, int)> calc_sizes = [&](int i, int p) {
      #ifdef DEBUG
      cout << "cs: " << i << '\n';
      #endif
      szs[i] = 1;
      for (int j : adj[i])
        if (j != p)
          szs[i] += calc_sizes(j, i);
      return szs[i];
    };
    calc_sizes(0, 0);
    function<void(int, int, ari2&, vt<int>&)> dfs = [&](int i, int p, ari2 &v, vt<int> &ans) {
      #ifdef DEBUG
      cout << "dfs: " << i << '\n';
      #endif
      if (!v[0])
        return;
      ans[i] = v[1];
      v[0]--;
      for (int j : adj[i])
        if (j != p)
          dfs(j, i, v, ans);
    };
    vt<int> ans(N, C[1]);
    bool found = false;
    function<void(int, int)> reroot = [&](int i, int p) {
      if (found)
        return;
      #ifdef DEBUG
      cout << "reroot " << i << '\n';
      #endif
      for (int j : adj[i])
        if (szs[i] - szs[j] >= A[0] && szs[j] >= B[0]) {
          dfs(i, j, A, ans);
          dfs(j, i, B, ans);
          found = true;
          return;
        }
      for (int j : adj[i])
        if (j != p) {
          int x = szs[j];
          szs[j] = N;
          szs[i] -= x;
          reroot(j, i);
          szs[i] += x;
          szs[j] = x;
        }
    };
    reroot(0, 0);
    if (found)
      return ans;
    return vt<int>(N, 0);
  }
  if (A[0] == 1) {
    bool seen[N] = {};
    int cnt = A[0] + B[0];
    function<void(int)> dfs = [&](int i) {
      if (seen[i] || !cnt)
        return;
      seen[i] = true;
      cnt--;
      for (int j : adj[i])
        dfs(j);
    };
    dfs(0);
    vt<int> adj2[N];
    FOR(i, 0, N-1)
      if (seen[i]) {
        #ifdef DEBUG
        cout << i << ' ';
        #endif
        for (int j : adj[i])
          if (seen[j])
            adj2[i].push_back(j);
      }
    #ifdef DEBUG
    cout << '\n';
    #endif
    int tin[N], low[N], timer = 0;
    memset(tin, -1, sizeof(tin));
    bool bad[N] = {};
    function<void(int, int)> dfs2 = [&](int i, int p) {
      low[i] = tin[i] = timer++;
      for (int j : adj2[i]) {
        if (j == p || !seen[j])
          continue;
        if (~tin[j])
          low[i] = min(low[i], tin[j]);
        else {
          dfs2(j, i);
          low[i] = min(low[i], low[j]);
          if (tin[i] <= low[j] && ~p) {
            bad[i] = true;
          }
        }
      }
      if (p < 0 && size(adj2[i]) > 1)
        bad[i] = true;
    };
    FOR(r, 0, N-1)
      if (seen[r]) {
        dfs2(r, -1);
        vt<int> ans(N, C[1]);
        int special;
        FOR(i, 0, N-1)
          if (seen[i]) {
            ans[i] = B[1];
            if (!bad[i])
              special = i;
          }
#ifdef DEBUG
        cout << "special node " << special << '\n';
#endif
        ans[special] = A[1];
        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:180:1: warning: control reaches end of non-void function [-Wreturn-type]
  180 | }
      | ^
split.cpp:176:20: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |         ans[special] = A[1];
      |                    ^

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