oj.uz

Submission #586190

# Submission time Handle Problem Language Result Execution time Memory
586190 2022-06-30T04:03:53 Z krit3379 Friend (IOI14_friend) C++17
46 / 100
 24 ms 4524 KB 
#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 dp[N][2],sum,ans;
bool f[3];
vector<int> g[N];

void dfs(int s,int f,int confidence[]){
    for(auto x:g[s]){
        if(x==f)continue;
        dfs(x,s,confidence);
        dp[s][1]+=dp[x][0];
        dp[s][0]+=max(dp[x][0],dp[x][1]);
    }
    dp[s][1]+=confidence[s];
    ans=max({ans,dp[s][0],dp[s][1]});
}

int findSample(int n,int confidence[],int host[],int protocol[]){
    int i,j,k;
    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,confidence[i]);
        else if(f[0]&&!f[1]&&!f[2]){
            for(i=1;i<n;i++)g[host[i]].push_back(i),g[i].push_back(host[i]);
            dfs(0,-1,confidence);
        }
    }
    else{

    }
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3412 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3584 KB Output is correct
6 Correct 2 ms 3440 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3432 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 3 ms 3540 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3412 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3364 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Incorrect 2 ms 3424 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3440 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3444 KB Output is correct
11 Correct 2 ms 3440 KB Output is correct
12 Incorrect 24 ms 4524 KB Output isn't correct
13 Halted 0 ms 0 KB -