Submission #297594

#	Time	Username	Problem	Language	Result	Execution time	Memory
297594		A02	Split the Attractions (IOI19_split)	C++14	18 / 100	138 ms	17404 KiB

split

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

using namespace std;

void root_tree(vector<vector<int> > &adjacent, int current, vector<int> &parents){

    for (int i = 0; i < adjacent[current].size(); i++){
        int child = adjacent[current][i];
        if (child != parents[current]){
            parents[child] = current;
            root_tree(adjacent, child, parents);
        }
    }
}

void calc_subtree_sizes(vector<vector<int> > &adjacent, int current, vector<int> &parents, vector<int> &subtree_sizes){

    for (int i = 0; i < adjacent[current].size(); i++){
        int child = adjacent[current][i];
        if (parents[child] == current){
            calc_subtree_sizes(adjacent, child, parents, subtree_sizes);
            subtree_sizes[current] += subtree_sizes[child];
        }
    }

}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {

	int m = q.size();

	vector<pair<int, int> > sets;
	sets.push_back(make_pair(a, 1));
	sets.push_back(make_pair(b, 2));
	sets.push_back(make_pair(c, 3));
	sort(sets.begin(), sets.end());
	a = sets[0].first;
	b = sets[1].first;
	c = sets[2].first;

	vector<int> res (n, sets[2].second);


	vector<vector<int> > adjacent (n, vector<int>());

	for (int i = 0; i < p.size(); i++){
        adjacent[p[i]].push_back(q[i]);
        adjacent[q[i]].push_back(p[i]);
	}

	if (m == n){

        int current = 0;
        int a_size = 1;
        int b_size = 0;
        res[current] = sets[0].second;

        while (a_size < a){
            if (res[adjacent[current][0]] == sets[2].second){
                current = adjacent[current][0];
                res[current] = sets[0].second;
            } else {
                current = adjacent[current][1];
                res[current] = sets[0].second;
            }
            a_size++;
        }

        while (b_size < b){
            if (res[adjacent[current][0]] == sets[2].second){
                current = adjacent[current][0];
                res[current] = sets[1].second;
            } else {
                current = adjacent[current][1];
                res[current] = sets[1].second;
            }
            b_size++;
        }

        return res;

	}

	if (a == 1){

        queue<int> to_visit;
        int b_size = 1;
        res[0] = sets[1].second;
        to_visit.push(0);

        while(b_size < b){

            int current = to_visit.front();
            to_visit.pop();

            for (int i = 0; i < adjacent[current].size(); i++){
                int next = adjacent[current][i];

                if (res[next] == sets[2].second && b_size < b){
                    res[next] = sets[1].second;
                    b_size++;
                    to_visit.push(next);
                }
            }
        }

        for (int i = 0; i < n; i++){
            if (res[i] == sets[2].second){
                res[i] = sets[0].second;
                break;
            }
        }

        return res;

	}

	if (m == n - 1){

        vector<int> parents (n, -1);
        vector<int> subtree_sizes (n, 1);

        root_tree(adjacent, 0, parents);
        calc_subtree_sizes(adjacent, 0, parents, subtree_sizes);

        for (int i = 0; i < n; i++){

            vector<pair<int, int> > i_subtree_sizes;

            if (i != 0){
                i_subtree_sizes.push_back(make_pair(n - subtree_sizes[i], parents[i]));
            }

            for (int j = 0; j < adjacent[i].size(); j++){
                int child = adjacent[i][j];
                i_subtree_sizes.push_back(make_pair(subtree_sizes[child], child));
            }

            for (int k = 0; k < i_subtree_sizes.size(); k++){
                int s_size = i_subtree_sizes[k].first;
                //cout << s_size << ' ' << b << endl;

                if (s_size >= b && n - s_size >= a){

                    queue<int> b_to_visit;

                    b_to_visit.push(i_subtree_sizes[k].second);

                    res[i_subtree_sizes[k].second] = sets[1].second;
                    res[i] = sets[0].second;

                    int b_size = 1;

                    while (b_size < b){

                        int current = b_to_visit.front();
                        b_to_visit.pop();

                        for (int j = 0; j < adjacent[current].size(); j++){
                            int next = adjacent[current][j];
                            if (res[next] == sets[2].second && b_size < b){
                                b_size++;
                                res[next] = sets[1].second;
                                b_to_visit.push(next);
                            }
                        }

                    }

                    queue<int> a_to_visit;

                    a_to_visit.push(i);

                    int a_size = 1;

                    while (a_size < a){

                        int current = a_to_visit.front();
                        a_to_visit.pop();

                        for (int j = 0; j < adjacent[current].size(); j++){
                            int next = adjacent[current][j];
                            if (res[next] == sets[2].second && a_size < a){
                                a_size++;
                                res[next] = sets[0].second;
                                a_to_visit.push(next);
                            }
                        }

                    }

                    return res;
                }
            }
        }

        return vector<int> (n, 0);
	}

	return vector<int> (n, 0);
}

Compilation message (stderr)

split.cpp: In function 'void root_tree(std::vector<std::vector<int> >&, int, std::vector<int>&)':
split.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i = 0; i < adjacent[current].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'void calc_subtree_sizes(std::vector<std::vector<int> >&, int, std::vector<int>&, std::vector<int>&)':
split.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < adjacent[current].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < p.size(); i++){
      |                  ~~^~~~~~~~~~
split.cpp:97:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for (int i = 0; i < adjacent[current].size(); i++){
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:135:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |             for (int j = 0; j < adjacent[i].size(); j++){
      |                             ~~^~~~~~~~~~~~~~~~~~~~
split.cpp:140:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |             for (int k = 0; k < i_subtree_sizes.size(); k++){
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:160:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |                         for (int j = 0; j < adjacent[current].size(); j++){
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:182:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |                         for (int j = 0; j < adjacent[current].size(); j++){
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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