Submission #237894

#	Time	Username	Problem	Language	Result	Execution time	Memory
237894		quocnguyen1012	Split the Attractions (IOI19_split)	C++14	100 / 100	234 ms	17648 KiB

split

#ifndef LOCAL
#include "split.h"
#endif // LOCAL
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

class DSU
{
public:
  vector<int> lab;
  DSU(int n)
  {
    lab.assign(n, -1);
  }
  int finds(int u)
  {
    if(lab[u] < 0) return u;
    return lab[u] = finds(lab[u]);
  }
  bool merges(int u, int v)
  {
    u = finds(u); v = finds(v);
    if(u == v) return false;
    if(lab[v] < lab[u]) swap(u, v);
    lab[u] += lab[v]; lab[v] = u;
    return true;
  }
  bool same(int u, int v)
  {
    return (finds(u) == finds(v));
  }
  int sz(int x)
  {
    return -lab[finds(x)];
  }
};

int sz[maxn], par[maxn];
vector<int> adj[maxn];

int findcen(int mxsize)
{
  function<void(int)> dfs = [&](int u)
  {
    sz[u] = 1;
    for(int v : adj[u]) if(v != par[u]){
      par[v] = u;
      dfs(v);
      sz[u] += sz[v];
    }
  };
  dfs(0);
  int u = 0;
  while(true){
    ii mx = mp(-1, -1);
    for(int v : adj[u]) if(v != par[u]){
      mx = max(mx, mp(sz[v], v));
    }
    if(mx.fi <= mxsize) return u;
    u = mx.se;
  }
  assert(0);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  DSU dsu(n);
  vector<int> col(n, 0);
  int m = p.size();
  int ca, cb, cc;
  {
    vector<ii> v;
    v.eb(a, 1); v.eb(b, 2); v.eb(c, 3);
    sort(v.begin(), v.end());
    tie(a, ca) = v[0]; tie(b, cb) = v[1];
    tie(c, cc) = v[2];
  }
  for(int i = 0; i < m; ++i){
    if(dsu.merges(p[i], q[i])){
      adj[p[i]].eb(q[i]);
      adj[q[i]].eb(p[i]);
    }
  }
  dsu = DSU(n);
  int r = findcen(n - b);
  for(int i = 0; i < n; ++i){
    for(int j : adj[i]){
      if(i != r && j != r){
        dsu.merges(i, j);
      }
    }
  }
  for(int i = 0; i < m; ++i){
    int u = p[i], v = q[i];
    if(dsu.sz(u) >= a || dsu.sz(v) >= a) continue;
    if(u == r || v == r) continue;
    if(dsu.merges(u, v)){
      adj[u].eb(v); adj[v].eb(u);
    }
  }

  function<void(int, int &, int, int)> go = [&](int u, int & need, int co, int bad)
  {
    if(u == bad || need == 0 || col[u] != 0) return;
    col[u] = co;
    --need;
    for(int v : adj[u]) go(v, need, co, bad);
  };
  for(int v : adj[r]) if(dsu.sz(v) >= a){
    go(v, a, ca, r);
    go(r, b, cb, -1);
    for(int i = 0; i < n; ++i)
      if(col[i] == 0) col[i] = cc;
    break;
  }
  return col;
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int n, m, a, b, c; cin >> n >> m >> a >> b >> c;
  vector<int> x(m), y(m);
  for(int i = 0; i < m; ++i) cin >> x[i];
  for(int i = 0; i < m; ++i) cin >> y[i];
  vector<int> res = find_split(n, a, b, c, x, y);
  for(auto & it : res) cout << it << ' ';
}
#endif // LOCAL

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