제출 #1218249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218249		Hamed_Ghaffari	Friend (IOI14_friend)	C++20	100 / 100	23 ms	6412 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;

#define SZ(x) int(x.size())

const int MXN = 1e5+5;

int dp[MXN][2], suf[MXN], pre[MXN];
vector<int> g[MXN];

int findSample(int n,int confidence[],int host[],int protocol[]) {
    for(int i=1; i<n; i++) g[host[i]].push_back(i);
    for(int v=n-1; v>=0; v--) {
        if(g[v].empty()) {
            dp[v][1] = confidence[v];
            continue;
        }
        for(int i=0; i<SZ(g[v]); i++) {
            pre[i] = i ? pre[i-1] : 0;
            pre[i] += (protocol[g[v][i]]==1) ? max(dp[g[v][i]][0], dp[g[v][i]][1]) : dp[g[v][i]][0];
        }
        for(int i=SZ(g[v])-1; i>=0; i--) {
            suf[i] = i+1<SZ(g[v]) ? suf[i+1] : 0;
            suf[i] += protocol[g[v][i]] ? dp[g[v][i]][0] : max(dp[g[v][i]][0], dp[g[v][i]][1]);
        }
        dp[v][0] = suf[0];
        dp[v][1] = pre[SZ(g[v])-1] + confidence[v];
        for(int i=0; i<SZ(g[v]); i++)
            if(protocol[g[v][i]])
                dp[v][1] = max(dp[v][1], dp[g[v][i]][1] + (i ? pre[i-1] : 0) + (i+1<SZ(g[v]) ? suf[i+1] : 0));
    }
    return max(dp[0][0], dp[0][1]);
}

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