Submission #1225423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225423		Hamed_Ghaffari	Split the Attractions (IOI19_split)	C++20	100 / 100	75 ms	27464 KiB

split

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

#define mins(x, y) (x = min(x, y))

const int MXN = 1e5+5;

int n, a, b, c, la, lb, lc;
vector<int> g[MXN], ch[MXN], ans;
bool mark[MXN], bad[MXN];
int h[MXN], mn[MXN], sz[MXN];
bool flag;

void dfs_mark(int v) {
    mark[v] = 1;
    for(int u : ch[v])
        dfs_mark(u);
}

void dfs(int v, int p=-1) {
    mn[v] = h[v] = p==-1 ? 0 : h[p]+1;
    sz[v] = 1;
    for(int u : g[v])
        if(h[u]==-1) {
            ch[v].push_back(u);
            dfs(u, v);
            sz[v] += sz[u];
            mins(mn[v], mn[u]);
        }
        else if(u!=p) mins(mn[v], h[u]);
    if(!flag && sz[v]>=a) {
        flag = 1;
        int sum=1;
        for(int u : ch[v])
            if(mn[u]>=h[v])
                sum += sz[u];
        if(sum>=a) {
            if(n-sum<a) return;
            mark[v] = 1;
            for(int u : ch[v])
                if(mn[u]>=h[v])
                    dfs_mark(u);
            if(sum>=b) {
                for(int i=0; i<n; i++)
                    mark[i] ^= 1;
            }
        }
        else {
            sum = sz[v];
            for(int u : ch[v])
                if(mn[u]<h[v] && sum-sz[u]>=a) {
                    bad[u] = 1;
                    sum -= sz[u];
                }
            mark[v] = 1;
            for(int u : ch[v])
                if(!bad[u])
                    dfs_mark(u);
        }
    }
}

void dfs_a(int v) {
    ans[v] = la;
    a--;
    for(int u : g[v])
        if(a && mark[u] && !ans[u])
            dfs_a(u);
}

void dfs_b(int v) {
    ans[v] = lb;
    b--;
    for(int u : g[v])
        if(b && !mark[u] && !ans[u])
            dfs_b(u);
}

vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
    ::n = n;
    a=aa, b=bb, c=cc;
    la=1, lb=2, lc=3;
    if(a>b) swap(a, b), swap(la, lb);
    if(b>c) swap(b, c), swap(lb, lc);
    if(a>b) swap(a, b), swap(la, lb);
    for(int i=0; i<p.size(); i++) {
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }
    memset(h, -1, sizeof(h));
    dfs(0);
    int v_a=-1, v_b=-1;
    for(int i=0; i<n; i++)
        (mark[i] ? v_a : v_b) = i;
    ans = vector<int>(n, 0);
    if(v_a==-1) return ans;
    dfs_a(v_a);
    dfs_b(v_b);
    assert(a==0);
    for(int &i : ans)
        if(!i)
            i = lc;
    return ans;
}

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