# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1184631 | droopy | Friend (IOI14_friend) | C++20 | 0 ms | 0 KiB |
// Jesu juva
#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vull vector<ull>
#define vb vector<bool>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvpii vector<vpii>
#define f(i,x,n) for(int i=x;i<n;i++)
#define fe(i,x,n) for (int i=x;i<=n;i++)
#define fr(i,x,n) for (int i=x;i>n;i--)
#define fre(i,x,n) for(int i=x;i>=n;i--)
#define fll(i,x,n) for (ll i=x;i<n;i++)
ll findSample(int n, int confidence[], int host[], int protocol[]) {
ll select[n], dont[n];
f(i,0,n) {
select[i] = confidence[i];
dont[i] = 0;
}
fre(i,n-1,1) {
int u = host[i];
int v = i;
if(protocol[i] == 0) { // host
select[u] = select[u] + dont[v];
dont[u] = max(dont[u] + dont[v], dont[u] + select[v]);
}
else if(protocol[i] == 1) { // friends of host BUT NOT HOST
select[u] = max({select[u] + select[v], select[u] + dont[v], dont[u] + select[v]});
dont[u] = dont[u] + dont[v];
}
else if(protocol[i] == 2) { // friend of host AND host
select[u] = max(select[u] + dont[v], dont[u] + select[v]);
dont[u] = dont[u] + dont[v];
}
}
return max(select[0], dont[0]);
}
/*int main() {
ios::sync_with_stdio(false);
cin.tie(0);
/*
int t;cin>>t;
while(t--){
}
*/
int n;
cin >> n;
int conf[n], host[n], prot[n];
f(i,0,n) {
cin >> conf[i];
}
f(i,1,n) {
cin >> host[i] >> prot[i];
}
cout << findSample(n,conf,host,prot) << endl;
}*/
// soli Deo gloria