Submission #1275947

#TimeUsernameProblemLanguageResultExecution timeMemory
1275947LeynaFriend (IOI14_friend)C++20
11 / 100
1097 ms131072 KiB
#include "friend.h" #include <bits/stdc++.h> using namespace std; /* SUBTASK 4 vector<int> take, not_take; vector<vector<int>> children; void dfs(int u, int confidence[]){ take[u] += confidence[u]; for (int v : children[u]){ dfs(v, confidence); take[u] += not_take[v]; not_take[u] += max(not_take[v], take[v]); } } // Find out best sample int findSample(int n,int confidence[],int host[],int protocol[]){ children.resize(n); for (int i=1; i<n; i++){ children[host[i]].push_back(i); } take = not_take = vector<int>(n); dfs(0, confidence); return max(take[0], not_take[0]); }*/ /* SUBTASK 2 int findSample(int n,int confidence[],int host[],int protocol[]){ int ans = 0; for (int i=0; i<n; i++) ans += confidence[i]; return ans; } */ /* int findSample(int n,int confidence[],int host[],int protocol[]){ int ans = 0; for (int i=0; i<n; i++) ans = max(confidence[i], ans); return ans; }*/ int findSample(int n,int confidence[],int host[],int protocol[]){ int ans = 0; vector<vector<int>> graph(n); for (int i=1; i<n; i++){ if (protocol[i] == 0 || protocol[i] == 2){ graph[host[i]].push_back(i); graph[i].push_back(host[i]); } if (protocol[i] == 1 || protocol[i] == 2){ for (int v : graph[host[i]]){ if (v != i){ graph[v].push_back(i); graph[i].push_back(v); } } } } /*for (int i=0; i<n; i++){ cout << i << ": "; for (int x : graph[i]) cout << x << " "; cout << endl; } for (int i=0; i<n; i++) cout << confidence[i] << " "; cout << endl; */ int res = 0; for (int i=0; i< (1 << n); i++){ //cout << "i: " << i << endl; bool possible = true; int val = 0; for (int u=0; u<n && possible; u++){ if ((i & (1 << u)) != 0){ for (int v : graph[u]){ if ((i & (1 << v)) != 0){ //cout << i << " " << u << " " << v << endl; possible = false; break; } } //cout << "test " << endl; val += confidence[u]; } } if (possible) { //cout << i << ": " << val << endl; res = max(res, val); } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...