Submission #1040512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040512		ProtonDecay314	Friend (IOI14_friend)	C++17	100 / 100	24 ms	10252 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

pll solve(ll i, const vll& c, const vvpll& adj, vpll& dp) {
    pll& ans = dp[i];
    
    if(ans.fi == -1ll) {
        ans.fi = c[i];
        ans.se = 0ll;

        for(ll ind = adj[i].size() - 1ll; ind >= 0; ind--) {
            ll j = adj[i][ind].fi;
            ll pr = adj[i][ind].se;

            pll recurs = solve(j, c, adj, dp);

            ll ins_pick = recurs.fi, ins_nopick = recurs.se;
            ll new_pick, new_nopick;
            if(pr == 0ll) {
                new_pick = ans.fi + ins_nopick;
                new_nopick = ans.se + max(ins_pick, ins_nopick);
            } else if (pr == 1ll) {
                new_pick = max(ans.fi + max(ins_pick, ins_nopick), ins_pick + ans.se);
                new_nopick = ans.se + ins_nopick;
            } else if(pr == 2ll) {
                new_pick = max(ans.fi + ins_nopick, ans.se + ins_pick);
                new_nopick = ans.se + ins_nopick;
            }

            ans.fi = new_pick;
            ans.se = new_nopick;
        }
    }

    return ans;
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
    vvpll adj;
    vll c;
    for(ll i = 0; i < n; i++) {
        vpll adjr;
        adj.pb(adjr);
        c.pb(confidence[i]);
    }

    for(ll i = 1; i < n; i++) {
        adj[(ll)host[i]].pb({i, (ll)protocol[i]});
    }

    vpll dp(n, {-1ll, -1ll});

    pll ans = solve(0ll, c, adj, dp);

	return max(ans.fi, ans.se);
}

Compilation message (stderr)

friend.cpp: In function 'pll solve(ll, const vll&, const vvpll&, vpll&)':
friend.cpp:56:20: warning: 'new_nopick' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |             ans.se = new_nopick;
      |             ~~~~~~~^~~~~~~~~~~~
friend.cpp:55:20: warning: 'new_pick' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |             ans.fi = new_pick;
      |             ~~~~~~~^~~~~~~~~~

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