Submission #810247

#TimeUsernameProblemLanguageResultExecution timeMemory
810247KerimFriend (IOI14_friend)C++17
46 / 100
21 ms4308 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 vis[N], col[N], matched[N]; void dfs0(int nd){ vis[nd] = 1; for (auto to: adj[nd]) if (!vis[to]){ col[to] = col[nd] ^ 1; dfs0(to); } } bool dfs1(int nd){ if (vis[nd]) return 0; vis[nd] = 1; for (auto x: adj[nd]){ if (matched[x] == -1 or dfs1(matched[x])){ matched[x] = nd; return 1; } } return 0; } int findSample(int n,int arr[],int host[],int protocol[]){ for (int i = 0; i < n; i++) adj[i].clear(); bool subtask1 = (n <= 10); bool subtask2 = true, subtask3 = true; bool subtask4 = true, subtask5 = true; // Build graph for (int i = 1; i < n; i++){ int v = host[i], p = protocol[i]; subtask4 &= (p == 0); subtask2 &= (p == 1); subtask3 &= (p == 2); subtask5 &= (p <= 1); 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 (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]); } else if(subtask5){ for (int i = 0; i < n; i++) vis[i] = col[i] = 0; dfs0(0); vector<int> L, R; for (int i = 0; i < n; i++){ if (!col[i]) L.pb(i); else R.pb(i); } // Kuhn's algorithm for (auto x: R) matched[x] = -1; for (auto x: L){ for (auto y: L) vis[y] = false; dfs1(x); } int MM = 0; for (auto x: R) MM += (matched[x] != -1); answer = n - MM; } 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...