Submission #261385

#	Time	Username	Problem	Language	Result	Execution time	Memory
261385		A02	Friend (IOI14_friend)	C++14	11 / 100	49 ms	2680 KiB

friend

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

using namespace std;

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;

	}

	return 1;
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:27:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < adjacent[h].size(); j++){
                                 ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:34:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < adjacent[h].size(); j++){
                                 ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:52:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int a = 0; a < candidate_set.size(); a++){
                                 ~~^~~~~~~~~~~~~~~~~~~~~~
friend.cpp:53:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int b = a + 1; b < candidate_set.size(); b++){
                                         ~~^~~~~~~~~~~~~~~~~~~~~~
friend.cpp:63: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: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31