Submission #404177

#TimeUsernameProblemLanguageResultExecution timeMemory
404177biggFriend (IOI14_friend)C++14
46 / 100
31 ms4972 KiB
#include "friend.h" #include<bits/stdc++.h> using namespace std; // Find out best sample const int MAXN = 1e5 + 10; vector<int> grafo[MAXN]; int dp[MAXN][5], v[MAXN], comp[MAXN], maxc[MAXN]; int mat[15][15]; void dfsc(int x, int p, int c){ comp[x] = c; for(int v : grafo[x]){ if(v == p) continue; dfsc(v, x, c); } } void dfs(int x, int p){ dp[x][0] = 0, dp[x][1] = v[x]; for(int v : grafo[x]){ if(v == p) continue; dfs(v, x); dp[x][0] += max(dp[v][0], dp[v][1]); dp[x][1] += dp[v][0]; } } int findSample(int n,int confidence[],int host[],int protocol[]){ int ans= 0; if(n <= 10){ for(int i = 1; i < n; i++){ if(protocol[i] == 0){ grafo[i].push_back(host[i]); grafo[host[i]].push_back(i); mat[i][host[i]] = mat[host[i]][i] = 1; } if(protocol[i] >= 1){ for(int v : grafo[host[i]]){ grafo[i].push_back(v); grafo[v].push_back(i); mat[i][v] = mat[v][i] = 1; } if(protocol[i] == 2){ grafo[i].push_back(host[i]); grafo[host[i]].push_back(i); mat[i][host[i]] = mat[host[i]][i] = 1; } } } for(int i = 0; i < (1<<n); i++){ int aq = 0; bool ok = 0; for(int v1 = 0; v1 < n; v1++){ for(int v2 = v1 + 1; v2 < n; v2++){ if((1<<v1) & i && (1<<v2) & i && mat[v1][v2]) ok = 1; } } if(ok) continue; for(int j = 0; j < n; j++){ if((1<<j) & i) aq += confidence[j]; } ans = max(ans, aq); } return ans; } if(protocol[1] == 1){ for(int i = 0; i < n; i++) ans += confidence[i]; return ans; } if(protocol[1] == 2){ for(int i = 0; i < n; i++) ans = max(ans, confidence[i]); return ans; } for(int i = 0; i < n; i++) v[i] = confidence[i]; for(int i = 1; i < n; i++){ grafo[host[i]].push_back(i); grafo[i].push_back(host[i]); } int c = 0; for(int i = 0; i < n; i++){ if(!comp[i]){ dfsc(i,i, ++c); } } for(int i = 0; i < n; i++){ dfs(i, i); maxc[comp[i]] = max(maxc[comp[i]], dp[i][1]); } for(int i = 1; i <= c; i++) ans += maxc[i]; return ans; }
#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...