이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 (appears[2] == 0){
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;
vertices[h].first = max(vertices[h].first, vertices[h].second);
}
if (p == 1){
vertices[h].first += vertices[i].first;
vertices[h].second += vertices[i].second;
}
return vertices[0].first;
}
}
return 1;
}
컴파일 시 표준 에러 (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++){
~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |