| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 208292 | Sorting | 친구 (IOI14_friend) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
const int kN = 1007;
vector<int> adj[kN];
pair<int, bool> dp[kN][2];
void solve(int u, bool can, int parent, int confidence[]){
if(dp[u][can].second)
return dp[u][can].first;
dp[u][can].second = true;
int &ans = dp[u][can].first;
ans = 0;
if(can){
curr_ans = confidence[u];
for(int to: adj[u]){
if(to == parent)
continue;
curr_ans += solve(to, false, u, confidence);
}
ans = max(ans, curr_ans);
}
curr_ans = 0;
for(int to: adj[u]){
if(to == par)
continue;
curr_ans += solve(to, true, u, confidence);
}
ans = max(ans, curr_ans);
return ans;
}
int findSample(int n, int confidence[], int host[], int protocol[]){
for(int i = 1; i < n; ++i){
adj[host[i]].push_back(i);
adj[i].push_back(i);
}
return solve(0, true, -1, confidence);
}
