Submission #417695

#	Time	Username	Problem	Language	Result	Execution time	Memory
417695		usachevd0	Split the Attractions (IOI19_split)	C++14	22 / 100	96 ms	13152 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;
vector<int> G[maxN];
int sz[maxN];
int par[maxN];

void dfs(int v, int p = -1) {
    sz[v] = 1;
    par[v] = p;
    for (int u : G[v])
        if (u != p) {
            dfs(u, v);
            sz[v] += sz[u];
        }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> eu, vector<int> ev) {
    int sizes[3] = {a, b, c};
    int m = eu.size();
    assert(m == n - 1);
    for (int i = 0; i < m; ++i) {
        G[eu[i]].push_back(ev[i]);
        G[ev[i]].push_back(eu[i]);
    }
    dfs(0);
    
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (i != j) {
                int a = sizes[i], b = sizes[j];
                
                for (int v = 1; v < n; ++v) {
                    if (sz[v] >= a && n - sz[v] >= b) {
                        vector<int> ans(n, 0);
                        int need;
                        function<void(int, int, int)> dfs1 = [&](int v, int p, int c) {
                            if (!need) return;
                            ans[v] = c;
                            --need;
                            for (int u : G[v])
                                if (u != p)
                                    dfs1(u, v, c);
                        };
                        need = a;
                        dfs1(v, par[v], i + 1);
                        need = b;
                        dfs1(par[v], v, j + 1);
                        int k = 0;
                        while (k == i || k == j)
                            ++k;
                        for (int v = 0; v < n; ++v)
                            if (!ans[v])
                                ans[v] = k + 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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36