Submission #422280

#	Time	Username	Problem	Language	Result	Execution time	Memory
422280		APROHACK	Friend (IOI14_friend)	C++14	8 / 100	4 ms	3660 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
vector<int>ady[100001];
bool recorrido[100001];
bool prendido[100001];
vector<int>conf;
// Find out best sample
long long dp(int node, bool cant){
	//cout<<node<<endl;
	if(!cant){
		for(auto i:ady[node]){
			if(prendido[i]){
				cant=true;
				break;
			}
		}
	}
	recorrido[node]=true;
	long long ret=0, ret2=conf[node];
	if(cant){
		for(auto i:ady[node]){
			if(!recorrido[i]){
				ret=max(ret, dp(i, false));
			}
		}
		recorrido[node]=false;
		//cout<<"c"<<node<<" "<<ret<<endl;
		return ret;
	}else{
		prendido[node]=true;
		for(auto i:ady[node]){
			if(!recorrido[i]){
				ret2=max(dp(i, true), ret2);
			}
		}
		prendido[node]=false;
		for(auto i:ady[node]){
			if(!recorrido[i]){
				ret=max(dp(i, false), ret);
			}
		}
		recorrido[node]=false;
		//cout<<"r"<<node<<" "<<max(ret, ret2)<<endl;
		return max(ret, ret2);
	}
}
int findSample(int n,int confidence[],int host[],int protocol[]){
	int ans=10;
	memset(prendido, false, sizeof prendido);
	memset(recorrido, false, sizeof recorrido);
	for(int i = 0 ; i < n ; i++){
		conf.PB(confidence[i]);
	}
	bool cass=false;
	for(int i = 1 ; i < n ; i++){
		if(protocol[i]==0){//IAmYourFriend
			ady[host[i]].PB(i);
			ady[i].PB(host[i]);
		}else if(protocol[i]==1){//MyFriendsAreYourFriends
			for(auto j:ady[host[i]]){
				ady[j].PB(i);
				ady[i].PB(j);
			}
		}else{
			for(auto j:ady[host[i]]){
				ady[j].PB(i);
				ady[i].PB(j);
			}
			ady[host[i]].PB(i);
			ady[i].PB(host[i]);
			cass=true;
		}
	}
	/*
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < ady[i].size() ; j++){
			cout<<ady[i][j]<<" ";
		}
		cout<<endl;
	}*/
	long long sum=0, mx=0;
		for(int i = 0 ; i < n ; i++){
			sum+=confidence[i];
		}
	if(!cass){
		return sum;
	}
	//return dp(1, false);
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:52:6: warning: unused variable 'ans' [-Wunused-variable]
   52 |  int ans=10;
      |      ^~~
friend.cpp:85:19: warning: unused variable 'mx' [-Wunused-variable]
   85 |  long long sum=0, mx=0;
      |                   ^~
friend.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
   93 | }
      | ^

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