oj.uz

Submission #261389

# Submission time Handle Problem Language Result Execution time Memory
261389 2020-08-11T17:00:13 Z A02 Friend (IOI14_friend) C++14
27 / 100
 40 ms 1528 KB 
#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;

	}

	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;

	}
	
	return 1;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 40 ms 1528 KB Output isn't correct
13 Halted 0 ms 0 KB -