# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1276153 | KindaGoodGames | 휴가 (IOI14_holiday) | C++20 | 0 ms | 0 KiB |
#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
struct UnionFind{
vector<int> par;
UnionFind(int n){
par.resize(n);
iota(par.begin(),par.end(),0);
}
int find(int i){
if(par[i] == i) return i;
return par[i] = find(par[i]);
}
void unite(int i, int j){
i = find(i);
j = find(j);
par[i] = j;
}
};
vector<int> arr,dpT, dpN;
vector<vector<int>> adj;
void DFS(int v){
dpT[v] = arr[v];
int oth1 = 0;
for(auto u : adj[v]){
DFS(u);
dpT[v] += dpN[u];
dpN[v] += dpT[u];
}
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
int ans=0;
adj.resize(n);
for(int i = 1; i < n; i++){
adj[host[i]].push_back(i);
}
arr.resize(n);
dpT.resize(n);
dpN.resize(n);
for(int i = 0; i < n; i++){
arr[i] = confidence[i];
}
DFS(0);
for(int i = 0; i < n; i++){
ans = max({ans, dpT[i], dpN[i]});
}
return ans;
}