Submission #280801

#	Time	Username	Problem	Language	Result	Execution time	Memory
280801		ajpiano	Friend (IOI14_friend)	C++17	100 / 100	59 ms	7416 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 wc = 0;
        int given = 0;
        int curg = 0;
        for(auto &a: edges[i]){
            if(pr[a] == 0){
                tc += dp[a].f;
                given += dp[a].s;
            }
            else if(pr[a] == 1) tc += dp[a].s;
            else wc += dp[a].s;
        }
        dp[i].s = tc + wc;
        dp[i].f = conf[i]+given+wc;
        int upl = 0;
        for(auto &a: edges[i]){
            if(pr[a] == 0){
                cc += dp[a].f;
                curg += dp[a].s;
            }else if(pr[a] == 1){
                cc += dp[a].s;
                upl += dp[a].f;
                dp[i].f = max(dp[i].f, upl + wc + max(tc-cc+curg,conf[i]+given));
            }else{
                dp[i].f = max(dp[i].f, dp[a].f + upl + wc - dp[a].s + tc-cc+curg);
            }
//            if(i == 0) cerr << a << " " << upl << " " << tc-cc << " " << dp[i].f << "\n";
        }
        dp[i].f = max(dp[i].f,dp[i].s);
//        cerr << i << ": " << dp[i].f << " " << dp[i].s << "\n";
    }
    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) << "\n";
//}
//
//int main()
//{
//    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt","r",stdin);
//    freopen("RPAns.txt","w",stdout);
//    int t; cin >> t;
//    while(t--) grader();
//    return 0;
//}

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