Submission #355377

#	Time	Username	Problem	Language	Result	Execution time	Memory
355377		rrrr10000	Friend (IOI14_friend)	C++14	100 / 100	38 ms	4332 KiB

friend

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define dame(a) {cout<<a<<endl;return 0;}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vvvp=vector<vvp>;
using vb=vector<bool>;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
int findSample(int n, int confidence[], int host[], int protocol[]){
    vp dp(n);
    rep(i,n)dp[i]=P(confidence[i],0);
    for(int i=n-1;i>0;i--){
        if(protocol[i]==0){
            dp[host[i]].fi+=dp[i].se;
            dp[host[i]].se+=dp[i].fi;
        }
        if(protocol[i]==1){
            dp[host[i]].fi+=dp[i].fi;
            dp[host[i]].se+=dp[i].se;
        }
        if(protocol[i]==2){
            dp[host[i]].fi=max(dp[host[i]].fi+dp[i].se,dp[host[i]].se+dp[i].fi);
            dp[host[i]].se+=dp[i].se;
        }
        chmax(dp[host[i]].fi,dp[host[i]].se);
    }
    return dp[0].fi;
}

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