Submission #404179

#	Time	Username	Problem	Language	Result	Execution time	Memory
404179		peuch	Friend (IOI14_friend)	C++17	23 / 100	2 ms	332 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 10;

int dp[MAXN][2];
int v[MAXN];
int cor[MAXN];

int marcB[MAXN];
int match[MAXN];

vector<int> ar[MAXN];
vector<int> grp[2];

bool dfs(int cur);

int findSample(int n,int confidence[],int host[],int protocol[]){
	
	for(int i = 0; i < n; i++)
		v[i] = confidence[i];
	
	grp[0].push_back(0);
	cor[0] = 0;
	for(int i = 1; i < n; i++){
		if(protocol[i] == 0){
			ar[host[i]].push_back(i);
			ar[i].push_back(host[i]);
			cor[i] = !cor[host[i]];
			grp[cor[i]].push_back(i);
		}
		else{
			for(int j = 0; j < ar[host[i]].size(); j++){
				ar[ar[host[i]][j]].push_back(i);
				ar[i].push_back(ar[host[i]][j]);
			}
			cor[i] = cor[host[i]];
			grp[cor[i]].push_back(i);
		}
	}
	
	for(int i = 0; i < n; i++)
		match[i] = -1;
	
	bool flag = true;
	int ans = 0;
	while(flag){
		flag = false;
		for(int i = 0; i < n; i++) marcB[i] = 0;
		for(int i = 0; i < grp[0].size(); i++){
			int cur = grp[0][i];
			if(match[cur] != -1) continue;
			if(dfs(cur)){
				flag = true;
				ans++;
			}		
		}
	}
	ans = n - ans;
	return ans;
}

bool dfs(int cur){
	for(int i = 0; i < ar[cur].size(); i++)	{
		int viz = ar[cur][i];
		if(marcB[viz]) continue;
		marcB[viz] = 1;
		if(match[viz] == -1 || dfs(match[viz])){
			match[cur] = viz;
			match[viz] = cur;
			return true;
		}
	}
	return false;
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for(int j = 0; j < ar[host[i]].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i = 0; i < grp[0].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
friend.cpp: In function 'bool dfs(int)':
friend.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = 0; i < ar[cur].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~

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