| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 702021 | PCTprobability | 친구 (IOI14_friend) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
using ll = long long;
#define pb push_back
vector<int> g[100000];
int dp[100000][2];
ll con[100000];
void dfs(int a,int b){
for(auto e:g[a]){
if(e==b) continue;
dfs(e,a);
dp[a][0]+=max(dp[e][0],dp[e][1]);
dp[a][1]+=dp[e][0];
}
dp[a][1]+=con[a];
}
int findSample(int n, int confidence[], int host[], int protocol[]){
for(int i=0;i<n;i++) con[i]=confidence[i];
bool alltwo=true;
for(int i=1;i<n;i++){
if(protocol[i]!=2) alltwo=false;
}
bool allonezero=true;
for(int i=1;i<n;i++){
if(protocol[i]==2) allonezero=false;
}
if(alltwo){
ll ans=0;
for(int i=0;i<n;i++) ans=max(ans,con[i]);
return ans;
}
if(allzeroone){
for(int i=1;i<n;i++){
if(protocol[i]==0){
g[host[i]].pb(i);
g[i].pb(host[i]);
}
if(protocol[i]==1){
con[host[i]]+=con[i];
}
}
dfs(0,-1);
return max(dp[0][0],dp[0][1]);
}
assert(n<=10);
vector<vector<int>> a(n,vector<int>(n));
for(int i=1;i<n;i++){
if(protocol[i]==0){
a[i][host[i]]=a[host[i]][i]=1;
}
if(protocol[i]==1){
for(int j=0;j<n;j++){
if(a[host[i]][j]){
a[i][j]=a[j][i]=1;
}
}
}
if(protocol[i]==2){
for(int j=0;j<n;j++){
if(a[host[i]][j]){
a[i][j]=a[j][i]=1;
}
}
a[i][host[i]]=a[host[i]][i]=1;
}
}
int ans=0;
for(int i=0;i<(1<<n);i++){
int sum=0,ok=1;
for(int j=0;j<n;j++){
if((i>>j)&1){
sum+=confidence[j];
for(int k=j+1;k<n;k++){
if((i>>k)&1){
if(a[j][k]) ok=0;
}
}
}
}
ans=max(ans,sum*ok);
}
return ans;
}