제출 #623427

#제출 시각아이디문제언어결과실행 시간메모리
623427yuto1115친구 (IOI14_friend)C++17
35 / 100
26 ms2616 KiB
#include "friend.h" #include <bits/stdc++.h> #define rep(i, n) for(ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i) #define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i) #define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i) #define pb push_back #define eb emplace_back #define SZ(a) int(a.size()) #define all(a) a.begin(), a.end() using namespace std; using ll = long long; using P = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vp = vector<P>; using vvp = vector<vp>; using vb = vector<bool>; using vvb = vector<vb>; using vs = vector<string>; const int inf = 1001001001; const ll linf = 1001001001001001001; template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } // Find out best sample int findSample(int n, int confidence[], int host[], int protocol[]) { if (n <= 10) { vvb G(n, vb(n)); rep2(nx, 1, n) { int i = host[nx]; if (protocol[nx] != 1) G[i][nx] = G[nx][i] = true; if (protocol[nx] != 0) { rep(j, n) { if (!G[i][j]) continue; G[j][nx] = G[nx][j] = true; } } } int mx = 0; rep(bit, 1 << n) { bool ok = true; rep(i, n) rep(j, n) { if ((bit >> i & 1) and (bit >> j & 1) and G[i][j]) ok = false; } if (!ok) continue; int now = 0; rep(i, n) if (bit >> i & 1) now += confidence[i]; chmax(mx, now); } return mx; } else if (*min_element(protocol + 1, protocol + n) == *max_element(protocol + 1, protocol + n)) { if (protocol[1] == 0) { vvi G(n); rep2(i, 1, n) { G[i].pb(host[i]); G[host[i]].pb(i); } auto dfs = [&](auto &dfs, int u, int p) -> P { P res(0, confidence[u]); for (int v: G[u]) { if (v == p) continue; P now = dfs(dfs, v, u); res.first += max(now.first, now.second); res.second += now.first; } return res; }; P ans = dfs(dfs, 0, -1); return max(ans.first, ans.second); } else if (protocol[1] == 1) { return accumulate(confidence, confidence + n, 0); } else { return *max_element(confidence, confidence + n); } } else { 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...