oj.uz

Submission #297594

# Submission time Handle Problem Language Result Execution time Memory
297594 2020-09-11T16:13:02 Z A02 Split the Attractions (IOI19_split) C++14
18 / 100
 138 ms 17404 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 0 ms 256 KB ok, correct split
5 Correct 0 ms 256 KB ok, correct split
6 Correct 1 ms 256 KB ok, correct split
7 Correct 129 ms 16040 KB ok, correct split
8 Correct 72 ms 7800 KB ok, correct split
9 Correct 138 ms 13068 KB ok, correct split
10 Correct 73 ms 7804 KB ok, correct split
11 Correct 83 ms 7800 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 97 ms 8952 KB ok, correct split
5 Correct 83 ms 8056 KB ok, correct split
6 Correct 73 ms 7800 KB ok, correct split
7 Correct 85 ms 7804 KB ok, correct split
8 Correct 137 ms 10232 KB ok, correct split
9 Correct 83 ms 7800 KB ok, correct split
10 Correct 59 ms 8308 KB ok, correct split
11 Correct 60 ms 8304 KB ok, correct split
12 Correct 65 ms 8304 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Runtime error 92 ms 17404 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 0 ms 256 KB ok, correct split
5 Correct 0 ms 256 KB ok, correct split
6 Correct 1 ms 256 KB ok, correct split
7 Correct 129 ms 16040 KB ok, correct split
8 Correct 72 ms 7800 KB ok, correct split
9 Correct 138 ms 13068 KB ok, correct split
10 Correct 73 ms 7804 KB ok, correct split
11 Correct 83 ms 7800 KB ok, correct split
12 Correct 0 ms 256 KB ok, correct split
13 Correct 1 ms 256 KB ok, correct split
14 Correct 1 ms 256 KB ok, correct split
15 Correct 97 ms 8952 KB ok, correct split
16 Correct 83 ms 8056 KB ok, correct split
17 Correct 73 ms 7800 KB ok, correct split
18 Correct 85 ms 7804 KB ok, correct split
19 Correct 137 ms 10232 KB ok, correct split
20 Correct 83 ms 7800 KB ok, correct split
21 Correct 59 ms 8308 KB ok, correct split
22 Correct 60 ms 8304 KB ok, correct split
23 Correct 65 ms 8304 KB ok, correct split
24 Correct 1 ms 256 KB ok, correct split
25 Runtime error 92 ms 17404 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -