Submission #261489

#	Time	Username	Problem	Language	Result	Execution time	Memory
261489		A02	Friend (IOI14_friend)	C++14	100 / 100	39 ms	3192 KiB

friend

#include "friend.h"
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <utility>
#include <set>

using namespace std;

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


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

        if (parents[adjacent[current][i]] == -1){
            parents[adjacent[current][i]] = current;
            rootTree(parents, adjacent[current][i], adjacent);
        }

    }

}

pair<int, int> calcBest (vector<int> &parents, vector<vector<int> > &adjacent, int current, int confidence[]){

    int best = confidence[current];
    int best_without = 0;

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

        if (parents[adjacent[current][i]] == current){
            pair<int, int> reduced = calcBest(parents, adjacent, adjacent[current][i], confidence);

            best += reduced.second;
            best_without += reduced.first;
        }

    }

    best = max(best, best_without);

    return make_pair(best, best_without);
}

int findSample(int n, int confidence[], int host[], int protocol[]){

	if (n <= 10){

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

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

            int h = host[i];
            int p = protocol[i];
            if (p == 0){
                adjacent[h].push_back(i);
                adjacent[i].push_back(h);
            }

            if (p == 1){
                for (int j = 0; j < adjacent[h].size(); j++){
                    adjacent[adjacent[h][j]].push_back(i);
                    adjacent[i].push_back(adjacent[h][j]);
                }
            }

            if (p == 2){
                for (int j = 0; j < adjacent[h].size(); j++){
                    adjacent[adjacent[h][j]].push_back(i);
                    adjacent[i].push_back(adjacent[h][j]);
                }
                adjacent[h].push_back(i);
                adjacent[i].push_back(h);
            }
        }
            int best = 0;
            for (int x = 0; x < (1 << n); x++){
                vector<int> candidate_set;
                for (int j = 0; j < n; j++){
                    if (x & (1 << j)){
                        candidate_set.push_back(j);
                    }
                }

                bool bad = false;
                for (int a = 0; a < candidate_set.size(); a++){
                    for (int b = a + 1; b < candidate_set.size(); b++){
                        if (find(adjacent[candidate_set[a]].begin(), adjacent[candidate_set[a]].end(), candidate_set[b]) != adjacent[candidate_set[a]].end()){
                            bad = true;
                        }
                    }
                }

                if (!bad){

                    int total = 0;
                    for (int a = 0; a < candidate_set.size(); a++){
                        total += confidence[candidate_set[a]];
                    }

                    best = max(best, total);
                }

            }
        return best;

	}

	int appears[3] = {0, 0, 0};
	for (int i = 1; i < n; i++){
        appears[protocol[i]] = 1;
	}

	if (appears[2] == 1 && appears[1] == 0 && appears[0] == 0){

        int best = 0;
        for (int i = 0; i < n; i++){
            best = max(best, confidence[i]);
        }
        return best;

	}

	if (appears[1] == 1 && appears[2] == 0 && appears[0] == 0){

        int best = 0;
        for (int i = 0; i < n; i++){
            best += confidence[i];
        }
        return best;

	}

	if (appears[1] == 0 && appears[2] == 0 && appears[0] == 1){


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

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

            int h = host[i];
            adjacent[h].push_back(i);
            adjacent[i].push_back(h);
        }

        vector<int> parents (n, -1);
        parents[0] = 0;
        rootTree(parents, 0, adjacent);
        return calcBest(parents, adjacent, 0, confidence).first;
	}

	if (true){

        vector<pair<int, int> > vertices (n, make_pair(1, 0));

        for (int i = 0; i < n; i++){
            vertices[i].first = confidence[i];
        }

        for (int i = n - 1; i > 0; i--){

            int h = host[i];
            int p = protocol[i];

            if (p == 0){

                vertices[h].first += vertices[i].second;
                vertices[h].second += vertices[i].first;

            }

            if (p == 1){

                vertices[h].first += vertices[i].first;
                vertices[h].second += vertices[i].second;

            }

            if (p == 2){

                vertices[h].first = max(vertices[h].first + vertices[i].second, vertices[h].second + vertices[i].first);
                vertices[h].second = vertices[h].second + vertices[i].second;

            }

            vertices[h].first = max(vertices[h].first, vertices[h].second);

        }

        return vertices[0].first;



	}

	return 1;
}

Compilation message (stderr)

friend.cpp: In function 'void rootTree(std::vector<int>&, int, std::vector<std::vector<int> >&)':
friend.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adjacent[current].size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
friend.cpp: In function 'std::pair<int, int> calcBest(std::vector<int>&, std::vector<std::vector<int> >&, int, int*)':
friend.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adjacent[current].size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:62:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < adjacent[h].size(); j++){
                                 ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:69:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < adjacent[h].size(); j++){
                                 ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:87:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int a = 0; a < candidate_set.size(); a++){
                                 ~~^~~~~~~~~~~~~~~~~~~~~~
friend.cpp:88:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int b = a + 1; b < candidate_set.size(); b++){
                                         ~~^~~~~~~~~~~~~~~~~~~~~~
friend.cpp:98:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int a = 0; a < candidate_set.size(); a++){
                                     ~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31