제출 #583444

#제출 시각아이디문제언어결과실행 시간메모리
583444thezomb1e친구 (IOI14_friend)C++17
27 / 100
184 ms65536 KiB
#include "friend.h" #include <bits/stdc++.h> #define eb emplace_back #define pb push_back #define ft first #define sd second #define pi pair<int, int> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define dbg(...) dbg_out(__VA_ARGS__) using ll = long long; using ld = long double; using namespace std; //Constants const ll INF = 5 * 1e18; const int IINF = 2 * 1e9; const ll MOD = 1e9 + 7; // const ll MOD = 998244353; const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; const ld PI = 3.14159265359; template<typename T> void mins(T& x, T y) {x = min(x, y);} template<typename T> void maxs(T& x, T y) {x = max(x, y);} vector<vector<int>> e; vector<int> a; int subtask1() { int n = a.size(); int ans = 0; for (int mask = 0; mask < (1 << n); mask++) { bool ok = true; int cur = 0; for (int i = 0; i < n; i++) { if (mask & (1 << i)) { cur += a[i]; for (int to : e[i]) { if (mask & (1 << to)) { ok = false; } } } } if (ok) maxs(ans, cur); } return ans; } int subtask2() { int ans = 0; for (int x : a) { ans += x; } return ans; } int subtask3() { int ans = 0; for (int x : a) { maxs(ans, x); } return ans; } int subtask4() { int ans = 0; int n = a.size(); vector<bool> vis(n + 5, false); vector<vector<int>> dp(n + 5, vector<int> (2, 0)); function<void(int)> dfs = [&](int f) { vis[f] = true; dp[f][1] += a[f]; for (int to : e[f]) { if (!vis[to]) { dfs(to); dp[f][0] += max(dp[to][1], dp[to][0]); dp[f][1] += dp[to][0]; } } }; for (int i = 0; i < n; i++) { if (!vis[i]) ans += max(dp[i][0], dp[i][1]); } return ans; } // Find out best sample int findSample (int n, int confidence[], int host[],int protocol[]){ e.resize(n + 5); a.resize(n); for (int i = 0; i < n; i++) a[i] = confidence[i]; bool sub1, sub2, sub3, sub4; sub1 = sub2 = sub3 = sub4 = true; for (int i = 1; i < n; i++) { sub2 &= protocol[i] == 1; sub3 &= protocol[i] == 2; sub4 &= protocol[i] == 0; if (protocol[i] == 0) { e[host[i]].pb(i); e[i].pb(host[i]); } else if (protocol[i] == 1) { for (int to : e[host[i]]) { e[to].pb(i); e[i].pb(to); } } else { for (int to : e[host[i]]) { e[to].pb(i); e[i].pb(to); } e[host[i]].pb(i); e[i].pb(host[i]); } } sub1 &= n <= 10; if (sub1) return subtask1(); else if (sub2) return subtask2(); else if (sub3) return subtask3(); else if (sub4) return subtask4(); return 0; }
#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...