Submission #418894

#	Time	Username	Problem	Language	Result	Execution time	Memory
418894		JediMaster11	Split the Attractions (IOI19_split)	C++17	0 / 100	148 ms	12632 KiB

split

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vint vector<int>
#define vll vector<long long>
#define fo(a, b, c) for (int a = b; a < (int)c; a++)
#define rfo(a, b, c) for (int a = b - 1; a >= (int)c; a--)
#define print(x) cout << x << "\n"

vint subtask1(int n, int a, int b, int c, vint p, vint q)
{

    vint ans;
    ans.reserve(n);

    int count = 0;
    int prev = -1;
    int on = p[0];
    int index = 0;
    int setOn = 0;

    vint lims;
    lims.push_back(a);
    lims.push_back(b);
    lims.push_back(c);

    do
    {
        count++;
        ans[on] = setOn + 1;

        if (count == lims[setOn])
        {

            setOn++;
            count = 0;
        }
        on = q[index++];

    } while (index != q.size());

    return ans;
}

vint subtask2(int n, int a, int b, int c, vll roads[])
{

    vint ans;

    int limit = 0, changeto = 0;
    if (b > c)
    { //do C

        ans.assign(n, 2);
        limit = c;
        changeto = 3;
    }
    else
    {
        ans.assign(n, 3);
        limit = b;
        changeto = 2;
    }

    //find b nodes connected, then change a random different node to a, let the rest be c

    set<int> visited;
    deque<int> toVisit; // node to visit

    int count = 0;

    toVisit.push_back(0);

    int on = -1;
    int prev = -1;

    while (count < limit)
    {

        while (toVisit.size() > 0)
        {
            prev = on;
            on = toVisit.back();
            toVisit.pop_back();

            visited.insert(on);
            count++;
            ans[on] = changeto;
            break;
        }

        for (auto x : roads[on])
        {
            if (x != prev && visited.count(x) == 0)
            {
                toVisit.push_back(x);
            }
        }
    }

    ans[toVisit.back()] = 1;

    return ans;
}

// n - number of attractions
// a, b, c - size of sets a, b, c
// p, q - length m arrays containing the starts and stops of all the roads
//return an array of length n, all zeros if not possible, otherwise 1, 2 or 3 in each space
vint find_split(int n, int a, int b, int c, vint p, vint q)
{

    vint ans;

    if (a == 1)
    {

        vll roads[n];

        fo(i, 0, p.size())
        {

            roads[p[i]].push_back(q[i]);
            roads[q[i]].push_back(p[i]);
        }

        ans = subtask2(n, a, b, c, roads);
    }
    else
    {

        ans = subtask1(n, a, b, c, p, q);
    }

    return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> subtask1(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     } while (index != q.size());
      |              ~~~~~~^~~~~~~~~~~
split.cpp:19:9: warning: unused variable 'prev' [-Wunused-variable]
   19 |     int prev = -1;
      |         ^~~~

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