Submission #1024977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024977		nvujica	Friend (IOI14_friend)	C++14	8 / 100	18 ms	5412 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 1010;

int sol[2];
int boja[maxn];
vector <int> v[maxn];
int con[maxn];

void dodaj(int a, int b){
	v[a].push_back(b);
	v[b].push_back(a);
}

void rek(int x, int b){
	boja[x] = b;
	sol[b] += con[x];
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(boja[x2] == -1) rek(x2, !b);
	}
}

int findSample(int n,int confidence[],int host[],int protocol[]){
	bool sve1 = 1, sve2 = 1;
	for(int i = 1; i < n; i++){
		sve1 &= (protocol[i] == 1);
		sve2 &= (protocol[2] == 1);
	}
	
	if(sve1){
		int sum = 0;
		for(int i = 0; i < n; i++){
			sum += confidence[i];
		}
		return sum;
	}
	
	if(sve2){
		int naj = 0;
		for(int i = 0; i < n; i++){
			naj = max(naj, confidence[i]);
		}
		return naj;
	}
	
	for(int i = 1; i < n; i++){
		if(protocol[i]){
			for(int j = 0; j < v[host[i]].size(); j++){
				int x = v[host[i]][j];
				dodaj(x, i);
			}
		}
		if(protocol[i] % 2 == 0) dodaj(host[i], i);
	}
	
//	cout << confidence[0] << ' ' << confidence[1] << endl;
	
	if(n <= 10){
		int ans = 0;
		
		for(int mask = 0; mask < (1 << n); mask++){
			int sum = 0;
			bool ok = 1;
			
			for(int i = 0; i < n; i++){
				if(!(mask & (1 << i))) continue;
				
				sum += confidence[i];
				
				for(int j = 0; j < v[i].size(); j++){
					int x = v[i][j];
					
					if(mask & (1 << x)){
//						cout << "tu " << mask << ' ' << i << ' ' << x << endl;
						ok = 0;
						break;
					}
				}
			}
			
//			cout << mask << ' ' << ok << ' ' << sum << endl;
			
			if(ok) ans = max(ans, sum);
		}
		
		return ans;
	}
	
	for(int i = 0; i < n; i++){
		con[i] = confidence[i];
	}
	
	int ans = 0;
	
	memset(boja, -1, sizeof boja);
	
	for(int i = 0; i < n; i++){
		if(boja[i] != -1) continue;
		
		rek(i, 0);
		ans += max(sol[0], sol[1]);
		sol[0] = 0;
		sol[1] = 0;
	}
	
	return ans;
}

//int main(){
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
//
//	int n;
//	cin >> n;
//	int confidence[n];
//	int host[n];
//	int protocol[n];
//	
//	for(int i = 0; i < n; i++){
//		cin >> confidence[i];
//	}
//	
//	for(int i = 1; i < n; i++){
//		cin >> host[i] >> protocol[i];
//	}
//	
//	cout << findSample(n, confidence, host, protocol);
//
//	return 0;
//}

Compilation message (stderr)

friend.cpp: In function 'void rek(int, int)':
friend.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int j = 0; j < v[host[i]].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
friend.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~

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