Submission #774012

#	Time	Username	Problem	Language	Result	Execution time	Memory
774012		Jarif_Rahman	Split the Attractions (IOI19_split)	C++17	40 / 100	66 ms	16460 KiB

split

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct dsu{
    int n;
    vector<int> sz, p;
    dsu(int nn){
        n = nn;
        sz.resize(n, 1);
        p.resize(n);
        for(int i = 0; i < n; i++) p[i] = i;
    }
    int get(int x){
        if(p[x] != x) p[x] = get(p[x]);
        return p[x];
    }
    bool unite(int a, int b){
        a = get(a), b  = get(b);
        if(a == b) return 0;
        if(sz[b] > sz[a]) swap(a, b);
        sz[a]+=sz[b];
        sz[b] = 0;
        p[b] = a;
        return 1;
    }
};

int n, m;
vector<int> s, so;
vector<vector<int>> v;
vector<int> sz;

vector<int> ans;

void pre_dfs(int nd, int ss = -1){
    for(int x: v[nd]) if(x != ss) pre_dfs(x, nd), sz[nd]+=sz[x];
}

int cnt;
void create_ans(int nd, int ss, int avoid, int id){
    if(cnt == 0) return;
    ans[nd] = id;
    cnt--;
    for(int x: v[nd]) if(x != ss && x != avoid && cnt) create_ans(x, nd, avoid, id);
}

void dfs(int nd, int ss = -1){
    if(ans.back()) return;
    if(sz[nd] >= s[0] && n-sz[nd] >= s[1]){
        fill(ans.begin(), ans.end(), so[2]+1);
        cnt = s[0];
        create_ans(nd, ss, -1, so[0]+1);
        cnt = s[1];
        create_ans(0, -1, nd, so[1]+1);
        return;
    }
    else if(sz[nd] >= s[1] && n-sz[nd] >= s[0]){
        fill(ans.begin(), ans.end(), so[2]+1);
        cnt = s[1];
        create_ans(nd, ss, -1, so[1]+1);
        cnt = s[0];
        create_ans(0, -1, nd, so[0]+1);
        return;
    }

    for(int x: v[nd]) if(x != ss && !ans.back()) dfs(x, nd);
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> P, vector<int> Q){
    n = _n;
    s = {_a, _b, _c};
    so = {0, 1, 2};
    sort(so.begin(), so.end(), [&](int a, int b){
        return s[a] < s[b];
    });
    sort(s.begin(), s.end());

    m = P.size();
    v.assign(n, {});
    sz.assign(n, 1);
    ans.assign(n, 0);

    dsu ds(n);

    for(int i = 0; i < m; i++) if(ds.unite(P[i], Q[i])) v[P[i]].pb(Q[i]), v[Q[i]].pb(P[i]);
    pre_dfs(0);

    if(s[0] == 1){
        fill(ans.begin(), ans.end(), so[2]+1);
        cnt = s[1];
        create_ans(0, -1, -1, so[1]+1);
        for(int i = 0; i < n; i++) if(ans[i] == so[2]+1){
            ans[i] = so[0]+1;
            break;
        }
        return ans;
    }

    dfs(0);

    return ans;
}

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