Submission #280161

#	Time	Username	Problem	Language	Result	Execution time	Memory
280161		ajpiano	Friend (IOI14_friend)	C++14	35 / 100	1 ms	512 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 upl = conf[i], ml = conf[i], bl = 0;
        for(auto &a: edges[i]){
            if(pr[a] == 0){
                upl += dp[a].s;
                bl += dp[a].f;
            }else if(pr[a] == 1){
                upl += dp[a].f;
                bl += dp[a].s;
            }else{
                upl += dp[a].s;
                ml = max(ml + dp[a].s, dp[a].f+bl);
                bl += dp[a].s;
            }
            ml = max({ml,upl,bl});
        }
        dp[i].f = ml;
        dp[i].s = bl;
    }
    return dp[0].f;
}

//void grader(){
//    int n; cin >> n;
//    vi 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