Submission #586033

#	Time	Username	Problem	Language	Result	Execution time	Memory
586033		krit3379	Friend (IOI14_friend)	C++17	11 / 100	25 ms	2192 KiB

friend

#include<bits/stdc++.h>
#include"friend.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005

int findSample(int n,int confidence[N],int host[N],int protocol[N]){
    int i,j,k;
    long long sum,ans=0;
    bool f[3];
    if(n<=10){
        bitset<15> vis[N];
        for(i=0;i<=n;i++)vis[i]=0;
        for(i=1;i<n;i++){
            if(protocol[i])for(j=0;j<n;j++)if(vis[host[i]][j])vis[i][j]=vis[j][i]=true;
            if(protocol[i]!=1)vis[i][host[i]]=vis[host[i]][i]=true;
        }
        for(i=0;i<(1<<n);i++){
            sum=0;
            for(j=0;j<n;j++){
                if(i&(1<<j)){
                    for(k=0;k<n;k++)if(vis[j][k]&&(i&(1<<k)))break;
                    if(k!=n)break;
                    sum+=confidence[j];
                }
            }
            if(j==n)ans=max(ans,sum);
        }
    }
    else if(n<=1000){
        for(i=1;i<n;i++)f[protocol[i]]=true;
        if(f[0]&&!f[1]&&!f[2])for(i=0;i<n;i++)ans+=confidence[i];
        else if(!f[0]&&f[1]&&!f[2])for(i=0;i<n;i++)ans=max(ans,(long long)confidence[i]);
        else if(!f[0]&&!f[1]&&f[2])ans=0;
    }
    else{

    }
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31