Submission #817035

#	Time	Username	Problem	Language	Result	Execution time	Memory
817035		vjudge1	Split the Attractions (IOI19_split)	C++17	7 / 100	82 ms	14760 KiB

split

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int sbt = 5;
vector<vector<int> > v;
vector<int> pa, st;
vector<bool> va;
int dfs(int i)
{
    va[i] = true;
    int s = 1;
    for (auto j : v[i])
    {
        if (j != pa[i] && !va[j])
        {
            pa[j] = i;
            s += dfs(j);
        }
    }
    return s;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    vector<pair<int, int> > o = {{a, 1}, {b, 2}, {c, 3}};
    vector<int> r(n, 0);
    sort(o.begin(), o.end());
    v.resize(n);
    pa.resize(n);
    st.resize(n);
    va.resize(n);
    int i, m = p.size();
    for (i = 0; i < m; i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }
    for (i = 0; i < n; i++)
    {
        pa[i] = -1;
        va[i] = false;
    }
    for (i = 0; i < n; i++)
    {
        if (v[i].size() > 2)
            break;
    }
    if (n <= 2500 && m <= 5000)
        sbt = 4;
    if (m == n - 1)
        sbt = 3;
    if (a == 1)
        sbt = 2;
    if (i == n)
        sbt = 1;
    if (sbt == 1)
    {
        int tf = -1, ts = -1, co = 0;
        for (i = 0; i < n; i++)
        {
            if (v[i].size() == 1)
            {
                if (tf == -1)
                    tf = i;
                else
                {
                    ts = i;
                    break;
                }
            }
        }
        if (i != n)
            dfs(tf);
        else
        {
            dfs(0);
            if (pa[v[0][0]] == 0)
                ts = v[0][1];
            else
                ts = v[0][0];
        }
        for (i = ts; i != -1; i = pa[i])
        {
            if (co < o[0].first)
                r[i] = o[0].second;
            else if (co < o[0].first + o[1].first)
                r[i] = o[1].second;
            else
                r[i] = o[2].second;
            co++;
        }
    }
    return r;
}

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