Submission #295625

#TimeUsernameProblemLanguageResultExecution timeMemory
295625stoyan_malininFriend (IOI14_friend)C++14
27 / 100
43 ms5112 KiB
#include "friend.h" //#include "grader.cpp" #include <vector> #include <cstring> #include <iostream> using namespace std; const int MAXN = 1005; int n; vector <int> graph[MAXN]; void constructGrahp(int n, int confidence[], int host[], int protocol[]) { for(int x = 1;x<=n;x++) { if(protocol[x]==0) { graph[ host[x] ].push_back(x); graph[x].push_back(host[x]); } else if(protocol[x]==1) { for(int y: graph[ host[x] ]) { graph[y].push_back(x); graph[x].push_back(y); } } else if(protocol[x]==2) { graph[x].push_back(host[x]); graph[ host[x] ].push_back(x); for(int y: graph[ host[x] ]) { graph[y].push_back(x); graph[x].push_back(y); } } } } namespace Subtask1 { bool can(int x, int mask) { for(int y: graph[x]) { if(((mask>>y)&1)==1) return false; } return true; } int rec(int x, int mask, int confidence[]) { if(x==n) return 0; int answer = rec(x+1, mask, confidence); if(can(x, mask)==true) answer = max(answer, confidence[x]+rec(x+1, (mask|(1<<x)), confidence)); return answer; } int solve(int n, int confidence[], int host[], int protocol[]) { return rec(0, 0, confidence); } }; namespace Subtask2 { int solve(int n, int confidence[], int host[], int protocol[]) { int ans = 0; for(int x = 0;x<n;x++) ans += confidence[x]; return ans; } }; namespace Subtask3 { int solve(int n, int confidence[], int host[], int protocol[]) { int ans = 0; for(int x = 0;x<n;x++) ans = max(ans, confidence[x]); return ans; } }; namespace Subtask4 { int memo[MAXN][2]; int rec(int x, int last, bool take, int confidence[]) { if(memo[x][take]!=-1) return memo[x][take]; int answer = 0; if(take==true) { answer += confidence[x]; for(int y: graph[x]) { if(y==last) continue; answer += rec(y, x, false, confidence); } } else { for(int y: graph[x]) { if(y==last) continue; answer += rec(y, x, true, confidence); } } memo[x][take] = answer; return answer; } int solve(int n, int confidence[], int host[], int protocol[]) { memset(memo, -1, sizeof(memo)); return max(rec(0, -1, false, confidence), rec(0, -1, true, confidence)); } }; int guessSubtask(int n, int confidence[], int host[], int protocol[]) { if(n<=10) return 1; bool subtask2 = true; for(int x = 1;x<n;x++) { if(protocol[x]!=1) { subtask2 = false; break; } } if(subtask2==true) return 2; bool subtask3 = true; for(int x = 1;x<n;x++) { if(protocol[x]!=2) { subtask3 = false; break; } } if(subtask3==true) return 3; bool subtask4 = true; for(int x = 1;x<n;x++) { if(protocol[x]!=0) { subtask4 = false; break; } } if(subtask4==true) return 4; return -1; } int findSample(int _n,int confidence[],int host[],int protocol[]) { n = _n; int subtask = guessSubtask(n, confidence, host, protocol); if(subtask==2) return Subtask2::solve(n, confidence, host, protocol); if(subtask==3) return Subtask3::solve(n, confidence, host, protocol); constructGrahp(n, confidence, host, protocol); if(subtask==1) return Subtask1::solve(n, confidence, host, protocol); if(subtask==1) return Subtask4::solve(n, confidence, host, protocol); return 0; }
#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...