제출 #817069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817069		vjudge1	Split the Attractions (IOI19_split)	C++17	18 / 100	62 ms	16048 KiB

split

#include <iostream>
#include <vector>
#include <queue>
#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++;
        }
    }
    else if (sbt == 2)
    {
        vector<bool> VAA(n);
        for (i = 0; i < n; i++)
            VAA[i] = false;
        for (i = 0; i < n; i++)
        {
            if (!va[i] && dfs(i) >= o[1].first)
            {
                for (int jj = 0; jj < n; jj++)
                    va[jj] = false;
                queue<int> q;
                q.push(i);
                va[i] = true;
                int seh = 0;
                while (!q.empty() && seh < o[1].first)
                {
                    seh++;
                    int tt = q.front();
                    if (seh <= o[1].first)
                    {
                        r[tt] = o[1].second;
                        VAA[tt] = true;
                    }
                    q.pop();
                    for (auto sg : v[tt])
                    {
                        if (!va[sg])
                        {
                            q.push(sg);
                            va[sg] = true;
                        }
                    }
                }
                break;
            }
        }
        bool ww = false;
        for (i = 0; i < n; i++)
        {
            if (!VAA[i] && !ww)
            {
                ww = true;
                r[i] = o[0].second;
            }
            else if (!VAA[i])
            {
                r[i] = o[2].second;
            }
        }
    }
    return r;
}

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