제출 #546477

#제출 시각아이디문제언어결과실행 시간메모리
546477emuyumi친구 (IOI14_friend)C++17
27 / 100
3 ms2792 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; bool link = 0; for (auto [to, t] : adj[v]){ dfs(to); if (t == 0){ vec.push_back({dp[to][0], dp[to][1]}); } else{ link = 1; if (t == 1){ val[v] += dp[to][1]; vec.push_back({dp[to][0], 0}); } else{ vec.push_back({dp[to][0], dp[to][1]}); } pii res = {0, 0}; for (auto [a, b] : vec){ res.first += a; res.second += b; } vec = {res}; } } if (!link){ dp[v][1] = val[v]; for (auto [a, b] : vec){ dp[v][0] += max(a, b); dp[v][1] += a; } } if (link){ for (auto [a, b] : vec){ dp[v][0] += a; dp[v][1] += max(a, b); } dp[v][1] = max(dp[v][1], dp[v][0] + 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...