Submission #546489

#TimeUsernameProblemLanguageResultExecution timeMemory
546489emuyumiFriend (IOI14_friend)C++17
35 / 100
3 ms2900 KiB
#include "friend.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int MN = 1e5 + 1, inf = 0x3f3f3f3f; int dp[MN][2], val[MN]; struct Edge{ int to, t; }; vector<Edge> adj[MN]; void dfs(int v){ vector<pii> vec = {{0, 0}}; for (auto [to, t] : adj[v]){ dfs(to); vec.push_back({dp[to][0], dp[to][1]}); if (t == 1 || t == 2){ if (t == 1){ val[v] += dp[to][1]; } pii res = {0, 0}; for (auto [a, b] : vec){ res.first += a; res.second = max(res.second, b); } vec = {res}; } } int tota = vec[0].first; dp[v][0] = vec[0].first; dp[v][1] = max(vec[0].first, vec[0].second); vec.erase(vec.begin()); for (auto [a, b] : vec){ tota += a; dp[v][0] += b; dp[v][1] += max(a, b); } dp[v][1] = max(dp[v][1], tota + val[v]); } int findSample(int n, int confidence[], int host[], int protocol[]){ for (int i = 0; i < n; ++i) val[i] = confidence[i]; for (int i = 1; i < n; ++i){ adj[host[i]].push_back({i, protocol[i]}); } dfs(0); // for (int i = 0; i < n; ++i) cout << i << ": " << dp[i][0] << " " << dp[i][1] << '\n'; return max(dp[0][0], dp[0][1]); }
#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...