Submission #730775

#	Time	Username	Problem	Language	Result	Execution time	Memory
730775		danikoynov	Split the Attractions (IOI19_split)	C++14	40 / 100	94 ms	17052 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int deg[maxn], m, n;
vector < int > graph[maxn];

int used[maxn];
vector < int > order;
void stick(int v)
{
    used[v] = 1;
    order.push_back(v);
    for (int u : graph[v])
    {
        if (!used[u])
            stick(u);
    }
}

void fill_component(int v, int sz)
{
    used[v] = 1;
    order.push_back(v);
    for (int u : graph[v])
    {
        if (order.size() == sz)
            break;
        if (!used[u])
        fill_component(u, sz);
    }
}

vector < int > split;
int t[3], A, B, C, sub[maxn];
bool done = false;
void dfs(int v, int p)
{
    sub[v] = 1;
    for (int u : graph[v])
    {
        if (done)
            break;
        if (u == p)
            continue;
        dfs(u, v);
        if (done)
            break;
        sub[v] += sub[u];
        if (sub[u] >= B && (n - sub[u]) >= A)
        {
            swap(A, B);
            swap(t[0], t[1]);
        }
        if (sub[u] >= A && (n - sub[u]) >= B)
        {
            done = true;
            used[v] = 1;
            fill_component(u, A);
            for (int d : order)
                split[d] = t[0];
            order.clear();
            used[v] = 0;
            fill_component(v, B);
            for (int d : order)
                split[d] = t[1];
            for (int i = 0; i < n; i ++)
                if (split[i] == 0)
                split[i] = t[2];
                break;
        }
    }
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
    n = N;
    m = p.size();
    for (int i = 0; i < p.size(); i ++)
    {
        graph[p[i]].push_back(q[i]);
        graph[q[i]].push_back(p[i]);
    }

    if (a == 1)
    {
        vector < int > res(n, 0);
        fill_component(0, b);
        for (int v : order)
            res[v] = 2;
        int sp = 0;
        while(res[sp] != 0)
            sp ++;
        res[sp] = 1;
        for (int i = 0; i < n; i ++)
            if (res[i] == 0)
            res[i] = 3;
        return res;
    }

    if (m == n - 1)
    {
        split.resize(n, 0);
        A = a;
        B = b;
        C = c;
        t[0] = 1;
        t[1] = 2;
        t[2] = 3;
        if (A > B)
        {
            swap(A, B);
            swap(t[0], t[1]);
        }
        if (A > C)
        {
            swap(A, C);
            swap(t[0], t[2]);
        }
        if (B > C)
        {
            swap(B, C);
            swap(t[1], t[2]);
        }

        dfs(0, -1);

        return split;
    }
    bool deg2 = true;
    for (int i = 0; i < m; i ++)
    {
        if (graph[i].size() > 2)
        {
            deg2 = false;
            break;
        }
    }

    int leaf = 0;
    while(leaf < n && graph[leaf].size() != 1)
        leaf ++;
    if (leaf == n)
        leaf = 0;
    stick(leaf);

    if (deg2)
    {
        vector < int > res(n);
        for (int i = 0; i < n; i ++)
        {
            int v = order[i];
            if (i < a)
                res[v] = 1;
            else
            if (i < a + b)
            res[v] = 2;
            else
                res[v] = 3;
        }
        return res;
    }
    else
    {
        vector < int > tmp;
        return tmp;
    }

}

Compilation message (stderr)

split.cpp: In function 'void fill_component(int, int)':
split.cpp:30:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         if (order.size() == sz)
      |             ~~~~~~~~~~~~~^~~~~
split.cpp: In function 'void dfs(int, int)':
split.cpp:70:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |             for (int i = 0; i < n; i ++)
      |             ^~~
split.cpp:73:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   73 |                 break;
      |                 ^~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < p.size(); i ++)
      |                     ~~^~~~~~~~~~

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