Submission #243653

#TimeUsernameProblemLanguageResultExecution timeMemory
243653KubinFriend (IOI14_friend)C++17
27 / 100
162 ms65540 KiB
#include <bits/stdc++.h> using namespace std; enum Protocol { IAmYourFriend = 0, MyFriendsAreYourFriends = 1, WeAreYourFriends = 2 }; int findSample(int _n, int val[], int host[], int protocol[]) { size_t n = _n; vector<vector<size_t>> graph(n); auto conn = [&](size_t u, size_t v) { graph[u].push_back(v); graph[v].push_back(u); }; uint mask = 0; for(size_t i = 1; i < n; i++) { mask |= 1<<protocol[i]; if(protocol[i] == IAmYourFriend) conn(i, host[i]); else if(protocol[i] == MyFriendsAreYourFriends) for(auto u : graph[host[i]]) conn(i, u); else if(protocol[i] == WeAreYourFriends) { for(auto u : graph[host[i]]) conn(i, u); conn(i, host[i]); } } if(not mask or mask == (1<<MyFriendsAreYourFriends)) return accumulate(val, val + n, 0); else if(mask == (1<<WeAreYourFriends)) return *max_element(val, val + n); /* else if(mask == (1<<IAmYourFriend)) { // host is parent } else if(mask == ((1<<IAmYourFriend) | (1<<MyFriendsAreYourFriends))) { // graph is bipartite } */ else { int result = 0; for(size_t s = 0; s < (1u << n); s++) { int curr = 0; bool ok = true; for(size_t i = 0; i < n; i++) if(s & (1 << i)) { curr += val[i]; for(size_t j = 0; j < n; j++) if(s & (1 << j)) if(find(graph[i].begin(), graph[i].end(), j) != graph[i].end()) ok = false; } if(ok) result = max(result, curr); } return result; } }
#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...