Submission #417986

#	Time	Username	Problem	Language	Result	Execution time	Memory
417986		usachevd0	Split the Attractions (IOI19_split)	C++14	40 / 100	133 ms	25520 KiB

split

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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}


const int maxN = 1e5 + 5;
int n;
vector<int> G[maxN], T[maxN], H[maxN];
bool used[maxN];
int comp[maxN], comps, csz[maxN], cfirst[maxN];
bool cused[maxN];
bool forA[maxN];

int dfs1(int v, int &c, int p = -1) {
    int sz = 1;
    used[v] = 1;
    for (int u : G[v]) {
        if (used[u] && u != p) continue;
        T[v].push_back(u);
        if (u == p) continue;
        sz += dfs1(u, c, v);
    }
    if (c == -1 && 2 * sz >= n)
        c = v;
    return sz;
}

void dfs2(int v, int c, int p = -1) {
    comp[v] = c;
    if (++csz[c] == 1)
        cfirst[c] = v;
    for (int u : T[v])
        if (u != p)
            dfs2(u, c, v);
}

vector<int> find_split(int _n, int A, int B, int C, vector<int> eu, vector<int> ev) {
    int m = eu.size();
    n = _n;
    int sizes[3] = {A, B, C};
    int sord[3] = {0, 1, 2};
    sort(sord, sord + 3, [&](int i, int j) -> bool {
        return sizes[i] < sizes[j];
    });
    
    A = sizes[sord[0]], B = sizes[sord[1]];
    
    for (int i = 0; i < m; ++i) {
        int u = eu[i], v = ev[i];
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    int c = -1;
    dfs1(0, c);
    if (c == -1)
        c = 0;
    
    comps = 0;
    comp[c] = -1;
    for (int v : T[c]) {
        dfs2(v, comps++, c);
    }
    
    // debug(c);
    // mdebug(comp, n);
    // for (int v = 0; v < n; ++v)
    //     for (int u : T[v])
    //         if (v < u)
    //             debug(v, u);
    
    // mdebug(csz, comps);
    
    if (*max_element(csz, csz + comps) >= A) {
        // cerr << "easy" << endl;
        int cl = max_element(csz, csz + comps) - csz;
        int v = cfirst[cl];
        vector<int> ans(n, 0);
        int need;
        function<void(int, int, int)> dfs = [&](int v, int c, int p) {
            if (need <= 0) return;
            --need;
            ans[v] = c;
            for (int u : T[v])
                if (u != p)
                    dfs(u, c, v);
        };
        need = A;
        dfs(v, sord[0] + 1, c);
        need = B;
        dfs(c, sord[1] + 1, v);
        for (int& x : ans)
            if (x == 0)
                x = sord[2] + 1;
        return ans;
    }
    
    for (int i = 0; i < m; ++i) {
        int u = eu[i], v = ev[i];
        if (u == c || v == c || comp[u] == comp[v]) continue;
        H[comp[u]].push_back(comp[v]);
        H[comp[v]].push_back(comp[u]);
    }
    for (int cl = 0; cl < comps; ++cl) {
        if (!cused[cl]) {
            int sz = 0;
            function<void(int)> dfsc = [&](int c) {
                cused[c] = 1;
                sz += csz[c];
                for (int d : H[c])
                    if (!cused[d])
                        dfsc(d);
            };
            dfsc(c);
            if (sz >= A) {
                int need = A;
                fill(cused, cused + comps, 0);
                function<void(int)> dfsc = [&](int c) {
                    if (need <= 0) return;
                    need -= csz[c];
                    cused[c] = 1;
                    forA[c] = 1;
                    for (int d : H[c])
                        if (!cused[d])
                            dfsc(d);
                };
                dfsc(cl);
                vector<int> ans(n, 0);
                function<void(int)> dfsa = [&](int v) {
                    if (need <= 0) return;
                    --need;
                    used[v] = 1;
                    ans[v] = sord[0] + 1;
                    for (int u : G[v])
                        if (!used[u] && u != c && forA[comp[u]])
                            dfsa(u);
                };
                need = A;
                fill(used, used + n, 0);
                dfsa(cfirst[cl]);
                function<void(int)> dfsb = [&](int v) {
                    if (need <= 0) return;
                    --need;
                    used[v] = 1;
                    ans[v] = sord[1] + 1;
                    for (int u : G[v])
                        if (!used[u] && !forA[comp[u]])
                            dfsb(u);
                };
                need = B;
                fill(used, used + n, 0);
                dfsb(c);
                for (int& x : ans)
                    if (x == 0)
                        x = sord[2] + 1;
                return ans;
            }
        }
    }
    return vector<int>(n, 0);
}


#ifdef LOCAL
int main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    
    int n, m, a, b, c;
    assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
    vector<int> p(m), q(m);
    for (int i=0; i<m; i++)
        assert(2 == scanf("%d%d", &p[i], &q[i]));
    fclose(stdin);

    vector<int> result = find_split(n, a, b, c, p, q);

    for (int i=0; i<(int)result.size(); i++)
        printf("%s%d", ((i>0)?" ":""), result[i]);
    printf("\n");
    fclose(stdout);
    return 0;

}
#endif

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