Submission #810224

#TimeUsernameProblemLanguageResultExecution timeMemory
810224KerimFriend (IOI14_friend)C++17
46 / 100
25 ms4436 KiB
#include "friend.h" #include "bits/stdc++.h" #define pb(x) push_back(x) using namespace std; const int N = 1005; vector<int> adj[N]; void add_edge(int u, int v){ adj[u].pb(v); adj[v].pb(u); } int dp[N][2]; void dfs(int nd, int pr, int val[]){ dp[nd][1] = val[nd]; dp[nd][0] = 0; for (auto c: adj[nd]){ if (c == pr) continue; dfs(c, nd, val); dp[nd][1] += dp[c][0]; dp[nd][0] += max(dp[c][0], dp[c][1]); } } int findSample(int n,int arr[],int host[],int protocol[]){ for (int i = 0; i < n; i++) adj[i].clear(); bool subtask2 = true, subtask3 = true; bool subtask4 = true; for (int i = 1; i < n; i++){ int v = host[i], p = protocol[i]; subtask4 &= (p == 0); subtask2 &= (p == 1); subtask3 &= (p == 2); if (p == 0)//IAmYourFriend add_edge(v, i); else if(p == 1){//MyFriendsAreYourFriends for (auto to: adj[v]) add_edge(to, i); } else{//WeAreYourFriends for (auto to: adj[v]) add_edge(to, i); add_edge(v, i); } } int answer = 0; if (n <= 10){//subtask1 for (int mask = 0; mask < (1<<n); mask++){ bool bad = 0; int sum = 0; for (int i = 0; i < n; i++) if (mask>>i&1){ sum += arr[i]; for (auto to: adj[i]) bad |= (mask>>to&1); } if (!bad) answer = max(answer, sum); } } else if(subtask2){ for (int i = 0; i < n; i++) answer += arr[i]; } else if (subtask3){ for (int i = 0; i < n; i++) answer = max(answer, arr[i]); } else if (subtask4){ dfs(0, -1, arr); answer = max(dp[0][0], dp[0][1]); } return answer; }
#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...