Submission #467141

#	Time	Username	Problem	Language	Result	Execution time	Memory
467141		ivan_tudor	Friend (IOI14_friend)	C++14	100 / 100	46 ms	8064 KiB

friend

#include<bits/stdc++.h>
// Define
const int N = 100005;
using namespace std;

int da[N], nu[N];
struct sonsh{
  int nod, pt;
};
vector<sonsh> sons[N];
int cost[N];
// Find out answer
void dfs(int nod){
  da[nod] = cost[nod];
  nu[nod] = 0;
  for(int i = sons[nod].size() - 1; i>=0; i--){
    int sn = sons[nod][i].nod;
    dfs(sn);
    int dah = 0, nuh = 0;
    if(sons[nod][i].pt == 0){ // IAmYourFriend
      dah = da[nod] + nu[sn];
      nuh = max(nu[nod] + nu[sn], nu[nod] + da[sn]);
    }
    else if(sons[nod][i].pt == 1){ // MyFriendsAreYourFriends
      dah = max({nu[nod] + da[sn], da[nod] + nu[sn], da[nod] + da[sn]});
      nuh = nu[nod] + nu[sn];
    }
    else if(sons[nod][i].pt == 2){ // We  AreYourFriends
      dah = max({nu[nod] + da[sn], da[nod] + nu[sn]});
      nuh = nu[nod] + nu[sn];
    }
    da[nod] = dah;
    nu[nod] = nuh;
  }

}
int findSample(int n,int confidence[],int host[],int protocol[]){
  for(int i = 0; i < n; i++)
    cost[i] = confidence[i];
  for(int i = 1; i < n; i++){
    sons[host[i]].push_back({i, protocol[i]});
  }
  dfs(0);
  return max(da[0], nu[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