제출 #431896

#제출 시각아이디문제언어결과실행 시간메모리
431896cfalas친구 (IOI14_friend)C++14
8 / 100
11 ms408 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second typedef pair<int, int> ii; #define FORi(i,a,b) for(int i=(int)a;i<(int)b;i++) #define FOR(i,n) FORi(i,0,n) #include "friend.h" typedef vector<int> vi; // Find out best sample vector<vi> adj; vi vis; int a[10000]; int dp[100000][2]; int dfs(int s, int p=-1, int cp=0){ if(dp[s][cp]) return dp[s][cp]; vis[s] = true; int ans1 = 0; int ans2=0; if(cp){ for(auto v : adj[s]) if(v!=p) ans1+=dfs(v, s, 0); } else{ for(auto v : adj[s]) if(v!=p) ans1+=dfs(v, s, 0); ans2 = a[s]; for(auto v : adj[s]) if(v!=p) ans2+=dfs(v, s, 1); } //cout<<s<<" "<<cp<<" "<<ans1<<" "<<ans2<<endl; dp[s][cp] = max(ans1, ans2); return max(ans1, ans2); } int ans1=0, ans2=0; void color(int s, int p=-1, int pc=0){ if(pc) ans1++; else ans2++; for(auto v : adj[s]) if(v!=p) color(v, s); } int findSample(int n,int confidence[],int host[],int protocol[]){ int ans=0; bool sub1=1, sub2=1; FORi(i,1,n) if(protocol[i]!=1) sub1 = false; FORi(i,1,n) if(host[i]!=1) sub2 = false; if(sub1) FOR(i,n) ans+=confidence[i]; else if(sub2) FOR(i,n) ans=max(ans, confidence[i]); else{ int tot=0; FOR(i,n) a[i] = confidence[i], tot+=a[i]; adj.assign(n+1, vi()); vis.assign(n+1, false); FORi(i,1,n){ adj[host[i]].push_back(i); adj[i].push_back(host[i]); } if(tot>n){ FOR(i,n) if(!vis[i]) ans+=dfs(i); } else{ FOR(i,n){ if(!vis[i]){ ans1 = 0; ans2 = 0; color(i); ans+= max(ans1,ans2); } } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...