Submission #655340

#	Time	Username	Problem	Language	Result	Execution time	Memory
655340		dooompy	Split the Attractions (IOI19_split)	C++17	100 / 100	96 ms	20220 KiB

split

    #include "split.h"
    #include<bits/stdc++.h>
    using namespace std;
    using ll = long long;
    #define fi first
    #define se second
    const int N = 1e5 + 5;
    vector<int> adj[N];
    int n, m; pair<int, int> x[3];
     
    int low[N], in[N], siz[N], par[N], t = 0;
    vector<int> ans;
    int dfs1(int u, pair<int, int>& x) {
      ans[u] = x.se; x.fi--;
      if (x.fi == 0) return 1;
      for (int v : adj[u]) if (par[v] == u)
        if (dfs1(v, x)) return 1;
      return 0;
    }
    int dfs2(int u, pair<int, int>& y) {
      ans[u] = y.se; y.fi--;
      if (y.fi == 0) return 1;
      for (int v : adj[u]) if (ans[v] == x[2].se)
        if (dfs2(v, y)) return 1;
      return 0;
    }
    int dfs(int u, int p = -1) {
      int flag = 1;
      in[u] = low[u] = ++t, siz[u] = 1;
      for (int v : adj[u]) if (v != p) {
        if (in[v]) low[u] = min(low[u], in[v]); // back-edge
        else {
          par[v] = u;
          if (dfs(v, u)) return 1;
          low[u] = min(low[u], low[v]);
          siz[u] += siz[v];
          flag &= siz[v] < x[0].fi;
        }
      }
      flag &= siz[u] >= x[0].fi;
      if (!flag) 
        return 0;
      int P1 = siz[u], P2 = n - siz[u];
      for (int v : adj[u]) if (par[v] == u && low[v] < in[u] && (P1 - siz[v]) >= x[0].fi)
        P1 -= siz[v], P2 += siz[v];
      if (P2 < x[0].fi) 
        return 0;
      if (P1 > P2) swap(x[0], x[1]);
      dfs1(u, x[0]); dfs2(p, x[1]);
      return 1;
    }
     
    vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
      n = _n; m = p.size();
      x[0] = {a, 1}, x[1] = {b, 2}, x[2] = {c, 3};
      sort(x, x + 3);
      for (int i = 0, u, v; i < m; ++i)
        u = p[i], v = q[i],
        adj[u].emplace_back(v),
        adj[v].emplace_back(u);
      ans = vector<int>(n, x[2].se);
      if (dfs(0)) 
        return ans;
      return vector<int>(n, 0);
    }

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