Submission #268726

#	Time	Username	Problem	Language	Result	Execution time	Memory
268726		doowey	Split the Attractions (IOI19_split)	C++14	100 / 100	207 ms	32512 KiB

split

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 10;
vector<int> T[N];
vector<int> R[N];
int subt[N];
pii S[3];
bool vis[N];

vector<int> nds[N];

void dfs(int u){
    vis[u]=true;
    subt[u]=1;
    for(auto x : T[u]){
        if(vis[x]) continue;
        dfs(x);
        subt[u] += subt[x];
        R[u].push_back(x);
        R[x].push_back(u);
    }
}

int id[N];
int sub[N];
int cnt;

void dfs1(int u, int cc){
    sub[u] = 1;
    id[u] = cc;
    nds[cc].push_back(u);
    for(auto x : R[u]){
        if(id[x] == -1){
            dfs1(x, cc);
            sub[u] += sub[x];
        }
    }
}

vector<int> spi;

void do_sp(int node, int ci){
    if(spi[node] > 0) return ;
    if(S[ci].fi > 0){
        S[ci].fi -- ;
        spi[node] = S[ci].se;
    }
    else{
        spi[node] = S[2].se;
    }
    for(auto x : R[node]){
        if((id[x] == id[node] || ci == 1) && spi[x] == 0){
            do_sp(x, ci);
        }
    }
}

vector<pii> C[N];
int sz[N];

vector<int> idi;
bool hvi[N];
int tot;

int curn;
int central;
bool has_sol;

void dfs2(int u){
    hvi[u]=true;
    idi.push_back(u);
    tot += sz[u];
    for(auto x : C[u]){
        if(hvi[x.fi]) continue;
        if(has_sol) return ;
        if(tot + sz[x.fi] >= S[0].fi){
            for(auto f : idi){
                do_sp(nds[f][0], 0);
            }
            do_sp(x.se, 0);
            do_sp(central, 1);
            has_sol = true;
            return ;
        }
        dfs2(x.fi);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    curn = n;
    int m = p.size();
    S[0] = mp(a, 1);
    S[1] = mp(b, 2);
    S[2] = mp(c, 3);
    sort(S, S + 3);
    spi.resize(n);
    for(int i = 0 ; i < m ; i ++ ){
        T[p[i]].push_back(q[i]);
        T[q[i]].push_back(p[i]);
    }
    dfs(0);
    int node = 0;
    int pp = -1;
    bool ok = true;
    while(ok){
        ok = false;
        for(auto x : R[node]){
            if(x != pp && subt[x] > n/2){
                pp = node;
                node = x;
                ok = true;
                break;
            }
        }
    }
    central = node;
    for(int i = 0 ; i < n; i ++ ){
        id[i] = -1;
    }
    id[node] = 0;
    for(auto x : R[node]){
        cnt ++ ;
        dfs1(x, cnt);
    }
    for(auto x : R[node]){
        if(sub[x] >= S[0].fi){
            do_sp(x, 0);
            do_sp(node, 1);
            for(int i = 0; i < n; i ++ ){
                if(spi[i] == 0) spi[i] = 3;
            }
            return spi;
        }
        sz[id[x]] = sub[x];
    }
    for(int i = 0 ;i < m ; i ++ ){
        if(id[p[i]] == 0 || id[q[i]] == 0 || id[p[i]] == id[q[i]]) continue;
        C[id[p[i]]].push_back(mp(id[q[i]], q[i]));
        C[id[q[i]]].push_back(mp(id[p[i]], p[i]));
    }
    for(int i = 1; i <= cnt; i ++ ){
        if(hvi[i]) continue;
        tot = 0;
        idi.clear();
        dfs2(i);
        if(has_sol){
            for(int j = 0 ; j < n; j ++ ){
                if(spi[j] == 0) spi[j] = S[2].se;
            }
            return spi;
        }
    }
    return spi;
}

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