Submission #50889

#TimeUsernameProblemLanguageResultExecution timeMemory
50889TalantFriend (IOI14_friend)C++17
27 / 100
74 ms25176 KiB
#include "friend.h" #include <bits/stdc++.h> #define pb push_back #define mk make_pair #define sc second #define fr first using namespace std; const int N = (1e6 + 5); int u[1005][1005]; int dp[1005][3]; int ans; int fg; vector <int> g[N]; void dfs (int v,int p = -1) { for (auto to : g[v]) { if (to != p) { dfs(to,v); dp[v][1] += dp[to][0]; dp[v][0] += max(dp[to][0],dp[to][1]); } } } int findSample(int n,int confidence[],int host[],int protocol[]){ if (n <= 10) { for (int i = 1; i < n; i ++) { int v = host[i]; if (protocol[i] == 0) { u[v][i] = 1,u[i][v] = 1; g[v].pb(i),g[i].pb(v); } else if (protocol[i] == 1) { for (auto to : g[v]) { g[to].pb(i),g[i].pb(to); u[to][i] = 1,u[i][to] = 1; } } else { for (auto to : g[v]) { g[to].pb(i),g[i].pb(to); u[to][i] = 1,u[i][to] = 1; } g[v].pb(i); g[i].pb(v); u[v][i] = 1; u[i][v] = 1; } } for (int i = 0; i < (1 << n); i ++) { vector <int> v; int fl = 0; int as = 0; for (int j = 0; j < n; j ++) { if (i & (1 << j)) { for (auto to : v) if (u[to][j]) fl = 1; as += confidence[j]; v.pb(j); } } if (!fl) ans = max(ans,as); } return ans; } else { if (protocol[1] == 1) { for (int i = 0; i < n; i ++) ans += confidence[i]; return ans; } else if (protocol[1] == 2) { for (int i = 0; i < n; i ++) ans = max(ans,confidence[i]); return ans; } else { for (int i = 0; i < n; i ++) dp[i][1] = confidence[i]; dfs(1); return max(dp[1][0],dp[1][1]); } } }
#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...