Submission #408836

#	Time	Username	Problem	Language	Result	Execution time	Memory
408836		idk321	Split the Attractions (IOI19_split)	C++17	22 / 100	579 ms	1048580 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);
    }
}

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]);
	}

	dfs(0, -1);
    findGood(0, -1);


	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:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < P.size(); i++)
      |                  ~~^~~~~~~~~~

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