제출 #586375

#제출 시각아이디문제언어결과실행 시간메모리
586375SeDunion친구 (IOI14_friend)C++17
0 / 100
1 ms688 KiB
#include "friend.h" #include<iostream> #include<assert.h> #include<vector> using namespace std; const int N = 1e4 + 123; vector<int>g[N]; int c[N]; int used[N]; void dfs(int v, int &a, int &b) { a += c[v]; used[v] = 1; for (int to : g[v]) if (!used[to]) { dfs(to, b, a); } } vector<int>vec; int pr[N]; void go(int v) { used[v] = 1; for (int to : g[v]) if (to != pr[v]) { if (used[to]) { if (vec.size()) continue; int y = v; while (y != to) { vec.emplace_back(y); y = pr[y]; } vec.emplace_back(to); } else { pr[to] = v; go(to); } } } int X[N], Y[N]; int dp[N][2]; int findSample(int n,int confidence[],int host[],int protocol[]){ for (int i = 0 ; i < n ; ++ i) { c[i] = confidence[i]; } for (int i = 1 ; i < n ; ++ i) { int j = host[i]; g[j].emplace_back(i); g[i].emplace_back(j); } int ans = 0; for (int i = 0 ; i < n ; ++ i) { if (used[i]) continue; vec.clear(); pr[i] = -1; go(i); for (int j = 0 ; j < n ; ++ j) used[j] = 0; if (!vec.size()) { int a = 0, b = 0; dfs(i, a, b); ans += max(a, b); continue; } for (int j : vec) used[j] = 1; int m = vec.size(); for (int j = 0 ; j < m ; ++ j) { dfs(vec[j], X[j], Y[j]); } dp[0][0] = Y[0]; dp[0][1] = 0; for (int j = 1 ; j < m ; ++ j) { dp[j][0] = max(dp[j - 1][0], dp[j - 1][1]) + Y[j]; dp[j][1] = dp[j - 1][0] + X[j]; } int cur = dp[m - 1][0]; cur = max(cur, dp[m - 1][1]); dp[0][0] = 0; dp[0][1] = X[0]; for (int j = 1 ; j < m ; ++ j) { dp[j][0] = max(dp[j - 1][0], dp[j - 1][1]) + Y[j]; dp[j][1] = dp[j - 1][0] + X[j]; } cur = max(cur, dp[m - 1][0]); ans += cur; } return ans; }
#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...