| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1019510 | pcc | 친구 (IOI14_friend) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
namespace BRUTE{
const int mxn = 11;
vector<int> paths[mxn];
int GO(int n,int wei[],int host[],int op[]){
for(int i = 1;i<n;i++){
int p = host[i];
if(op[i] == 0){
paths[i].push_back(p);
}
else if(op[i] == 1){
paths[i] = paths[p];
}
else{
paths[i] = paths[p];
paths[i].push_back(p);
}
for(auto &j:paths[i])paths[j].push_back(i);
}
int ans = 0;
for(int i = 0;i<(1<<n);i++){
bool flag = true;
int sum = 0;
for(int j = 0;j<n;j++){
if(!(i&(1<<j)))continue;
sum += wei[j];
for(auto nxt:paths[j]){
if(i&(1<<nxt))flag = false;
}
}
if(!flag)continue;
ans = max(ans,sum);
}
return ans;
}
}
namespace TREE{
const int mxn = 1e5+10;
vector<int> tree[mxn];
int arr[mxn];
int dp[mxn][2];
int ans;
void dfs(int now){
dp[now][0] = dp[now][1] = 0;
for(auto nxt:tree[now]){
dfs(nxt);
dp[now][0] += max(dp[nxt][0],dp[nxt][1]);
dp[now][1] += dp[nxt][0];
}
dp[now][1] += arr[now];
ans = max({ans,dp[now][0],dp[now][1]});
return;
}
int GO(int n,int wei[],int host[],int op[]){
int ans = 0;
for(int i = 0;i<n;i++)arr[i] = wei[i];
for(int i = 1;i<n;i++){
asset(host[i]<i&&host[i]>=0);
tree[host[i]].push_back(i);
}
dfs(0);
return ans;
}
}
// Find out best sample
int findSample(int n,int wei[],int host[],int op[]){
if(n<=10)return BRUTE::GO(n,wei,host,op);
else if(op[1] == 0)return TREE::GO(n,wei,host,op);
else if(op[2] == 1){
int re = 0;
for(int i = 0;i<n;i++)re += wei[i];
return re;
}
else return *max_element(wei,wei+n);
}