Submission #447139

#	Time	Username	Problem	Language	Result	Execution time	Memory
447139		marsxiang5902	Split the Attractions (IOI19_split)	C++14	100 / 100	211 ms	25796 KiB

split

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define F first
#define S second
const int MN = 1e5+5, MM = 2e5+5;

int N, M, asz, bsz;

struct dsu{
    int sz[MN]{}, par[MN]{};
    int top(int u){ return par[u] ? par[u] = top(par[u]) : u; }
    bool merge(int u, int v){
        u = top(u); v = top(v);
        if(u == v) return 0;
        if(sz[u] > sz[v]) swap(u, v);
        par[u] = v; sz[v] += sz[u];
        return 1;
    }
} dsu1, dsu2;

vector<int> adjl[MN], adjl_all[MN];

namespace centroid{
    int sz[MN]{}, col[MN];
    void dfs1(int u, int p){
        sz[u] = 1;
        for(int v: adjl[u]){
            if(v != p){
                dfs1(v, u);
                sz[u] += sz[v];
            }
        }
    }
    int find_centroid(int u, int p){
        for(int v: adjl[u]){
            if(v != p){
                if(sz[v] << 1 > N) return find_centroid(v, u);
            }
        } return u;
    }
    void dfs2(int u, int p, int c){
        ++sz[c];
        col[u] = c;
        for(int v: adjl[u]){
            if(v != p){
                dfs2(v, u, c);
            }
        }
    }
}

namespace stage_3{
    vector<int> adjl2[MN];
    bool vis[MN]{};
    vector<int> explored;
    int tot_sz;
    void dfs(int u){
        if(tot_sz >= asz) return;
        tot_sz += centroid::sz[u];
        explored.push_back(u);
        vis[u] = 1;
        for(int v: adjl2[u]){
            if(!vis[v]){
                dfs(v);
            }
        }
    }
}

namespace get_ans{
    bitset<MN> allowed{}; vector<int> *ans; int c, cnt;
    void dfs(int u, int p){
        if(--cnt < 0){
            return;
        }
        ans->at(u-1) = c;
        for(int v: adjl_all[u]){
            if(ans->at(v-1) == 0 && allowed[centroid::col[v]]){
                dfs(v, u);
            }
        }
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> adjf, vector<int> adjs){
    N = n; M = adjf.size();
    pii ord[3] = {{a,1}, {b,2}, {c,3}};
    sort(ord, ord+3);
    asz = ord[0].F; bsz = ord[1].F;

    for(int z: {0,1}){
        vector<int> &vec = z ? adjf : adjs;
        for(int &v: vec){
            ++v;
        }
    }
    for(int i = 0, u, v; i < M; i++){
        u = adjf[i]; v = adjs[i];
        if(dsu1.merge(u, v)){
            adjl[u].push_back(v);
            adjl[v].push_back(u);
        }
        adjl_all[u].push_back(v);
        adjl_all[v].push_back(u);
    }
    centroid::dfs1(1, -1);
    int cent = centroid::find_centroid(1, -1);
    memset(centroid::sz, 0, sizeof centroid::sz);

    auto find_ans = [&](vector<int> as)->vector<int>{
        using namespace get_ans;
        vector<int> ret(N);
        for(int v: as){
            allowed.set(v);
        } get_ans::c = ord[0].S; cnt = asz; ans = &ret;
        dfs(as[0], cent);
        
        allowed.flip(); get_ans::c = ord[1].S; cnt = bsz;
        dfs(cent, -1);

        for(int &v: ret){
            if(!v){
                v = ord[2].S;
            }
        }
        return ret;
    };

    for(int u: adjl[cent]){
        centroid::dfs2(u, cent, u);
        if(centroid::sz[u] >= asz){
            return find_ans({u});
        }
    }
    for(int i = 0, u, v; i < M; i++){
        u = adjf[i]; v = adjs[i];
        if(u == cent || v == cent) continue;
        u = centroid::col[u]; v = centroid::col[v];
        if(dsu2.merge(u, v)){
            stage_3::adjl2[u].push_back(v);
            stage_3::adjl2[v].push_back(u);
        }
    }
    for(int u: adjl[cent]){
        if(!stage_3::vis[u]){
            stage_3::explored.clear(); stage_3::tot_sz = 0;
            stage_3::dfs(u);
            if(stage_3::tot_sz >= asz){
                return find_ans(stage_3::explored);
            }
        }
    }

    return vector<int>(N);
}

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