| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1032233 | tolbi | Friend (IOI14_friend) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define tol(bi) (1LL<<((int)(bi)))
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
if (n<=1000){
bool prot0=false;
bool prot1=false;
bool prot2=false;
for (int i = 1; i < n; ++i)
{
if (protocol[i]==0) prot0=true;
if (protocol[i]==1) prot1=true;
if (protocol[i]==2) prot2=true;
}
vector<vector<int>> arr(n);
for (int i = 1; i < n; i++){
if (protocol[i]==0){
arr[host[i]].push_back(i);
arr[i].push_back(host[i]);
}
else if (protocol[i]==1){
for (auto &fr : arr[host[i]]){
arr[fr].push_back(i);
arr[i].push_back(fr);
}
}
else {
for (auto &fr : arr[host[i]]){
arr[fr].push_back(i);
arr[i].push_back(fr);
}
arr[host[i]].push_back(i);
arr[i].push_back(host[i]);
}
}
if (n<=10){
//subtask1
int ret = 0;
for (int i = 0; i < tol(n); i++){
int cur = 0;
for (int j = 0; j < n; j++){
if (tol(j)&i){
cur+=confidence[j];
for (auto &nex : arr[j]){
if (tol(nex)&i){
cur=0;
break;
}
}
if (cur==0) break;
}
}
ret=max(ret,cur);
}
return ret;
}
if (prot1 && !prot0 && !prot2){
//subtask2
int ret = 0;
for (int i = 0; i < n; ++i)
{
ret+=confidence[i];
}
return ret;
}
if (prot2 && !prot0 && !prot1){
//subtask3
int ret = 0;
for (int i = 0; i < n; ++i){
ret=max(ret,confidence[i]);
}
return ret;
}
if (prot0 && !prot1 && !prot2){
//subtask4
vector<array<int,2>> dp(n,{-1,-1});
function<int(int,int,int)> f = [&](int node, int lnode, int flag)->int{
if (dp[node][flag]!=-1) return dp[node][flag];
dp[node][flag]=0;
for (auto &nex : arr[node]){
if (nex==lnode) continue;
dp[node][flag]+=f(nex,node,0);
}
if (flag==1){
return dp[node][flag];
}
int nn = confidence[node];
for (auto &nex : arr[node]){
if (nex==lnode) continue;
nn+=f(nex,node,1);
}
return dp[node][flag]=max(dp[node][flag],nn);
};
return f(0,-1,0);
}
if (prot0 && prot1 && !prot2){
//subtask5
vector<array<int,2>> dp(n,{0,0});
dp[0][1]=confidence[0];
for (int i = 1; i < n; i++){
if (protocol[i]==0){
dp[i][1]=dp[host[i][0]]+confidence[i];
dp[i][0]=max(dp[host[i][0]],dp[host[i][1]]);
}
else {
dp[i][1]=dp[host[i][1]]+confidence[i];
dp[i][0]=max(dp[host[i][0]],dp[host[i][0]]);
}
}
}
return max(dp[n-1][0],dp[n-1][1]);
}
return 23;
}