이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int> adj[100005];
ll dp[100005][2],conf[100005],color[100005],N;
int prot[100005],ho[100005];
bool flag0,flag1,flag2,flag3;
// Find out best sample
void solve(int node,int p){
dp[node][1]=conf[node];
for(auto it:adj[node]){
if(it==p)continue;
solve(it,node);
dp[node][0]+=max(dp[it][0],dp[it][1]);
dp[node][1]+=dp[it][0];
}
}
void construct(){
for (int i = 1; i < N; ++i)
{
if(prot[i]==0){
adj[ho[i]].insert(i);
adj[i].insert(ho[i]);
}
else if(prot[i]==1){
for(auto it:adj[ho[i]])
adj[i].insert(it),adj[it].insert(i);
}
else{
adj[ho[i]].insert(i);
adj[i].insert(ho[i]);
for(auto it:adj[ho[i]])
adj[i].insert(it),adj[it].insert(i);
}
}
}
int findSample(int n,int confidence[],int host[],int protocol[]){
N=n;
color[0]=-1,conf[0]=confidence[0];
if(conf[0]!=1)flag3=1;
for (int i = 1; i < n; ++i)
{
prot[i]=protocol[i];
ho[i]=host[i];
color[i]=-1;
conf[i]=confidence[i];
if(conf[i]!=1)flag3=1;
if(protocol[i]==0)
flag0=1;
else if(protocol[i]==1)
flag1=1;
else flag2=1;
}
ll ans=0;
if(n<=10){
construct();
for (int mask = 0; mask < (1<<n); ++mask)
{
vector<int> vec;
ll sum=0;
bool f=1;
for (int j = 0; j < n; ++j)
{
if((mask>>j) &1){
for(auto it:vec)
if(adj[it].find(j)!=adj[it].end()){f=0;break;}
if(!f)break;
sum+=confidence[j],vec.push_back(j);
}
}
if(f)ans=max(ans,sum);
}
}
else if(!flag0 && !flag1){
for (int i = 0; i < n; ++i)
ans=max(ans,(ll)confidence[i]);
}
else if(!flag0 && !flag2){
for (int i = 0; i < n; ++i)
ans+=confidence[i];
}
else if(!flag1 && !flag2){
construct();
solve(0,0);
ans=max(dp[0][0],dp[0][1]);
}
else if(!flag2 && !flag3){
construct();
for (int i = 0; i < n; ++i)
if(color[i]==-1){
//cerr<<i<<"\n";
int a=0,b=0;
queue<int> q;
q.push(i);
color[i]=0;
while(!q.empty()){
int f=q.front();
q.pop();
if(!color[f])a++;
else b++;
for(auto it:adj[f]){
if(color[it]!=-1)assert(color[it]!=color[f]);
else color[it]=1-color[f],q.push(it);
}
}
//cerr<<a<<","<<b<<"\n";
ans+=max(a,b);
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |