Submission #408840

#	Time	Username	Problem	Language	Result	Execution time	Memory
408840		idk321	Split the Attractions (IOI19_split)	C++17	33 / 100	104 ms	15748 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

int a, b, c, n;
int colSz[4];

const int N = 200005;
vector<int> res;
vector<int> adj[N];
int good[N];

void colour(int node, int par, int& cur, int col)
{
    if (cur == 0) return;
    res[node] = col;
    cur--;
    for (int next : adj[node])
    {
        if (next == par) continue;
        colour(next, node, cur, col);
    }
}

void colour2(int node, int& cur, int col)
{
    if (cur == 0) return;
    res[node] = col;
    cur--;
    for (int next : adj[node])
    {
        if (res[next] != 0) continue;
        colour2(next, cur, col);
    }
}

int sz[N];

void dfs(int node, int par)
{
    sz[node] = 1;
    for (int next : adj[node])
    {
        if (next == par) continue;
        dfs(next, node);
        sz[node] += sz[next];
    }
}

void findGood(int node, int par)
{
    if (res[0] != 0) return;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {

            if (i == j) continue;
            if (sz[node] >= colSz[i] && n - sz[node] >= colSz[j])
            {
                colour(node, par, colSz[i], i);
                colour(par, node, colSz[j], j);

                int k = 1;
                for (; k == i || k == j; k++);
                for (int l = 0; l < n; l++) if (res[l] == 0) res[l] = k;

                return;
            }


        }
    }

    for (int next : adj[node])
    {
        if (next == par) continue;
        findGood(next,node);
    }
}


vector<int> find_split(int n1, int A, int B, int C, vector<int> P, vector<int> Q) {
    n = n1;
    a =A;
    b = B;
    c = C;
    colSz[1] = a;
    colSz[2] = b;
    colSz[3] = c;
	res.resize(n);
	for (int i = 0; i < P.size(); i++)
	{
        adj[P[i]].push_back(Q[i]);
        adj[Q[i]].push_back(P[i]);
	}


	if (P.size() == n - 1)
	{
        dfs(0, -1);
        findGood(0, -1);
	} else if (a == 1)
	{
        colour2(0, colSz[2], 2);
        for (int i = 0; i < n; i++)
        {
            if (res[i] == 0)
            {
                res[i] = 1;
                break;
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (res[i] == 0)
            {
                res[i] = 3;
            }
        }
	}



	return res;
}

/*
11 10
2 5 4
0 1
1 2
1 3
3 4
3 5
6 7
6 8
0 6
8 9
8 10
*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (int i = 0; i < P.size(); i++)
      |                  ~~^~~~~~~~~~
split.cpp:99:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |  if (P.size() == n - 1)
      |      ~~~~~~~~~^~~~~~~~

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