제출 #313516

#제출 시각아이디문제언어결과실행 시간메모리
313516kylych03친구 (IOI14_friend)C++14
46 / 100
241 ms65540 KiB
#include "friend.h" #include <bits/stdc++.h> //#include "grader.cpp" using namespace std; // Find out best sample bool f[3]; vector <int> g[100001]; int dp[100001][2]; int con[100001]; int vis[100001]; int cnt ; int cnt1; void dfs1(int v, int p, int x){ cnt++; cnt1+=(x%2); vis[v]=1; for(auto to : g[v] ){ if(to==p || vis[p]) continue; dfs1(to, v, x+1); } } void dfs(int v, int p){ int ans1=0, ans2=0; for(auto to : g[v] ){ if(to==p) continue; dfs(to, v); ans1+=dp[to][0]; ans2+=max(dp[to][0], dp[to][1]); } dp[v][1] = max( ans1 + con[v], ans2); dp[v][0] = ans2; } int findSample(int n,int confidence[],int host[],int protocol[]){ int sum=0, mx=0; f[0]=f[1]=f[2]=false; bool flag=true; for(int i = 1 ; i < n;i++){ f[protocol[i]]=true; } for(int i =0; i < n; i++){ con[i]=confidence[i]; if(con[i]!=1) flag=false; sum +=confidence[i]; mx = max(mx, confidence[i] ); } if( f[0]==false && f[2]==false ) return sum; if( f[0]==false && f[1]==false ) return mx; for(int i = 1 ; i <n ;i++){ if(protocol[i]==0){ g[host[i]].push_back(i); g[i].push_back(host[i]); } if(protocol[i]==1){ for(auto j : g[host[i]]){ g[i].push_back(j); g[j].push_back(i); } } if(protocol[i]==2){ for(auto j : g[host[i]]){ g[i].push_back(j); g[j].push_back(i); } g[host[i]].push_back(i); g[i].push_back(host[i]); } } if( f[1]==false && f[2]==false ){ dfs(0,-1); return max(dp[0][0], dp[0][1]); } if(n<=10){ for(int j = 0 ; j< (1<<n) ;j++){ bool res=true; sum = 0; for(int k = 0; k < n ;k++){ if(j & (1<<k)){ sum+=confidence[k]; for(int t = k+1 ; t < n; t++){ if(j &(1 << t)){ for(int s:g[k]) if(s==t){ res=false; break; } } } } } if(res) mx = max (mx, sum); } return mx; } if(flag){ int sum =0; for(int i = 0 ; i < n ; i++){ if(vis[i]==0){ cnt = 0 ; cnt1 =0; dfs1(i, -1, 0); sum+=max(cnt -cnt1, cnt1); } } return sum; } }

컴파일 시 표준 에러 (stderr) 메시지

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^
#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...