제출 #280412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
280412		ajpiano	친구 (IOI14_friend)	C++14	35 / 100	52 ms	7424 KiB

friend

#include <bits/stdc++.h>
#include <friend.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

using namespace std;

#define FOR(a,b) for(int a=0;a<b;a++)
#define F0R(a,b,c) for(int a = b; a<=c; a++)
#define f first
#define s second
#define m0(x) memset(x,0,sizeof(x))

typedef pair<int,int> pi;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pi> vpi;

int findSample(int n, int conf[], int host[], int pr[]){
    vi edges[n];
    F0R(i,1,n-1) edges[host[i]].push_back(i);
    vpi dp(n);
    for(int i = n-1; i >= 0; i--){
        int tc = 0, cc = 0;
        int given = 0;
        for(auto &a: edges[i]){
            if(pr[a] == 0){
                tc += dp[a].f;
                given += dp[a].s;
            }
            else tc += dp[a].s;
        }
        dp[i].s = tc;
        dp[i].f = conf[i];
        int upl = 0;
        for(auto &a: edges[i]){
            if(pr[a] == 0){
                cc += dp[a].f;
            }else if(pr[a] == 1){
                cc += dp[a].s;
                upl += dp[a].f;
                dp[i].f = max(dp[i].f, upl + max(tc-cc,conf[i]));
            }else{
                cc += dp[a].s;
                dp[i].f = max(dp[i].f, dp[a].f + upl + tc-cc);
            }
        }
        dp[i].f += given;
        dp[i].f = max(dp[i].f,dp[i].s);
    }
    return dp[0].f;
}
//
//void grader(){
//    int n; cin >> n;
//    int conf[n],host[n],pr[n];
//    FOR(i,n) cin >> conf[i];
//    F0R(i,1,n-1) cin >> host[i] >> pr[i];
//    cout << "Answer: " << findSample(n,conf,host,pr);
//}
//
//int main()
//{
//    ios_base::sync_with_stdio(0); cin.tie(0);
//    grader();
//    return 0;
//}

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