Submission #1286911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286911		tvgk	Split the Attractions (IOI19_split)	C++20	Compilation error	0 ms	0 KiB

split

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define uid(a, b) uniform_int_distribution<long long>(a, b)(rng);

struct edge
{
    int u, v, id;
};

int dsu[mxN], n, m, ans[mxN], cnt[mxN], root;
bool tt;
ii sz[mxN];
vector<int> w[mxN];
vector<edge> a;

int Find(int j)
{
    if (dsu[j] < 0)
        return j;
    else
        return dsu[j] = Find(dsu[j]);
}

bool Union(int u, int v)
{
    u = Find(u);
    v = Find(v);

    if (u == v)
        return 0;

    dsu[u] += dsu[v];
    dsu[v] = u;
    return 1;
}

void LOAN(int j, int par, int tt)
{
    if (sz[tt].fi)
    {
        sz[tt].fi--;
        ans[j] = tt;
    }

    for (int i : w[j])
    {
        if (i == par)
            continue;
        LOAN(i, j, tt);
    }
}

void DFS(int j, int par)
{
    cnt[j] = 1;
    for (int i : w[j])
    {
        if (i == par)
            continue;

        DFS(i, j);
        cnt[j] += cnt[i];
    }

    if (root == -1 && cnt[j] >= sz[1].fi)
        root = j;

    if (!tt && cnt[j] >= sz[1].fi && n - cnt[j] >= sz[2].fi)
    {
        tt = 1;
        LOAN(j, par, 1);
        LOAN(par, j, 2);
    }

    if (!tt && cnt[j] >= sz[2].fi && n - cnt[j] >= sz[1].fi)
    {
        tt = 1;
        LOAN(j, par, 2);
        LOAN(par, j, 1);
    }
}

void Part2()
{
    for (int i = 0; i < n; i++)
    {
        dsu[i] = -1;
        cnt[i] = 0;
        w[i].clear();
    }

    for (edge i : a)
    {
        if (i.u == root || i.v == root)
            i.id = 0;

        if (!i.id)
            continue;

        if (Union(i.u, i.v))
        {
            w[i.u].push_back(i.v);
            w[i.v].push_back(i.u);
        }
    }

    for (edge i : a)
    {
        if (i.u == root || i.v == root)
            continue;

        if (Union(i.u, i.v))
        {
            w[i.u].push_back(i.v);
            w[i.v].push_back(i.u);
        }

        if (dsu[Find(i.u)] <= -sz[1].fi)
            break;
    }

    for (edge i : a)
    {
        if ((i.u == root || i.v == root) && Union(i.u, i.v))
        {
            w[i.u].push_back(i.v);
            w[i.v].push_back(i.u);
        }
    }
    DFS(0, -1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);

    cin >> n >> m;

    for (int i = 1; i <= 3; i++)
    {
        cin >> sz[i].fi;
        sz[i].se = i;
    }
    sort(sz + 1, sz + 4);

    for (int i = 0; i < n; i++)
    {
        dsu[i] = -1;
        ans[i] = 3;
    }

    for (int i = 1; i <= m; i++)
    {
        edge tmp;
        cin >> tmp.u >> tmp.v;
        a.push_back(tmp);
    }

    for (int i = 0; i < a.size(); i++)
    {
        if (Union(a[i].u, a[i].v))
        {
            w[a[i].u].push_back(a[i].v);
            w[a[i].v].push_back(a[i].u);
            a[i].id = 1;
        }
    }
    root = -1;
    DFS(0, -1);

    if (!tt)
        Part2();

    for (int i = 0; i < n; i++)
        cout << sz[ans[i]].se * tt << " ";
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccqSgveH.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4ye1qk.o:split.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccqSgveH.o: in function `main':
grader.cpp:(.text.startup+0x270): undefined reference to `find_split(int, int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status