제출 #229603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229603		combi1k1	Split the Attractions (IOI19_split)	C++14	100 / 100	156 ms	18040 KiB

split

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

using namespace std;

#define ll  long long
#define ld  double

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

#define pb  emplace_back
#define X   first
#define Y   second

typedef pair<int,int>   ii;

const int   N   = 2e5 + 5;

int p[N];
int s[N];

int init(int n) {
    iota(p,p + n,0);
    fill(s,s + n,1);
    return  1;
}
int lead(int x) {   return  p[x] == x ? x : p[x] = lead(p[x]);  }
int join(int x,int y)   {
    x = lead(x);
    y = lead(y);

    if (x == y) return  0;
    if (s[x] < s[y])
        swap(x,y);
    
    p[y] = x;
    s[x] += s[y];

    return  1;
}
bool sameSet(int x,int y)   {
    x = lead(x);
    y = lead(y);

    return  x == y;
}
typedef vector<int> vec;

int findRoot(int mxSize,const vector<vec> &adj) {
    vector<int> s(sz(adj),0);
    vector<int> p(sz(adj),-1);
    
    function<void(int)> dfs = [&](int u)    {
        s[u] = 1;

        for(int v : adj[u]) if (v != p[u])  {
            p[v] = u;   dfs(v);
            s[u] += s[v];
        }
    };
    dfs(0);
    
    for(int u = 0 ;;)   {
        int siz = -1;
        int idx = 0;

        for(int v : adj[u]) if (v != p[u])
            if (siz < s[v])
                siz = s[v],
                idx = v;
        
        if (siz <= mxSize)  return  u;
        u = idx;
    }
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) {
    vector<int> res(n,0);
    vector<ii>  color_Set;

    color_Set.pb(a,1);
    color_Set.pb(b,2);
    color_Set.pb(c,3);
    
    sort(all(color_Set));

    a = color_Set[0].X; int ca = color_Set[0].Y;
    b = color_Set[1].X; int cb = color_Set[1].Y;
    c = color_Set[2].X; int cc = color_Set[2].Y;

    vector<vec> g(n);
    init(n);
    
    for(int i = 0 ; i < sz(p) ; ++i)
        if (join(p[i],q[i]))    {
            g[p[i]].pb(q[i]);
            g[q[i]].pb(p[i]);
        }
    init(n);
    int r = findRoot(n - b,g);

    for(int i = 0 ; i < n ; ++i)
    for(int x : g[i])   {
        if (i == r) continue;
        if (x == r) continue;

        join(i,x);
    }
    
    for(int i = 0 ; i < sz(p) ; ++i)    {
        int x = p[i];
        int y = q[i];

        if (sameSet(x,y))   continue;
        if (x == r) continue;
        if (y == r) continue;

        if (s[lead(x)] >= a)    continue;
        if (s[lead(y)] >= a)    continue;

        join(x,y);

        g[x].pb(y);
        g[y].pb(x);
    }
    function<void(int,int&,int,int)> cal = [&](int u,int&n,int c,int bad)   {
        if (u == bad)   return;
        if (res[u])     return;
        if (n == 0)     return;

        res[u] = c;
        n--;

        for(int v : g[u])
            cal(v,n,c,bad);
    };
    for(int v : g[r])   if (s[lead(v)] >= a)    {
        cal(v,a,ca,r);
        cal(r,b,cb,-1); // color root and its surrounding subgraph for set B
        
        replace(all(res),0,cc);
        break;
    }
    return  res;
}

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