Submission #417689

#	Time	Username	Problem	Language	Result	Execution time	Memory
417689		usachevd0	Split the Attractions (IOI19_split)	C++14	18 / 100	112 ms	16228 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];

vector<int> find_split(int n, int a, int b, int c, vector<int> eu, vector<int> ev) {
    int m = eu.size();
    vector<int> deg(n, 0);
    for (int i = 0; i < m; ++i) {
        ++deg[eu[i]];
        ++deg[ev[i]];
        G[eu[i]].push_back(ev[i]);
        G[ev[i]].push_back(eu[i]);
    }
    int s = min_element(all(deg)) - deg.begin();
    vector<char> used(n, false);
    vector<int> ord;
    function<void(int)> dfs = [&](int v) {
        used[v] = true;
        ord.push_back(v);
        for (int u : G[v])
            if (!used[u])
                dfs(u);
    };
    dfs(s);
    vector<int> ans(n);
    for (int i = 0; i < a; ++i)
        ans[ord[i]] = 1;
    for (int i = 0; i < b; ++i)
        ans[ord[a + i]] = 2;
    for (int i = 0; i < c; ++i)
        ans[ord[a + b + i]] = 3;
    return ans;
}


#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: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36