Submission #586519

#	Time	Username	Problem	Language	Result	Execution time	Memory
586519		Red_Inside	Friend (IOI14_friend)	C++17	23 / 100	5 ms	5972 KiB

friend

#define __MAXSIZE__ 100002

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define IOS ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define all(v) v.begin(), v.end()
#define pb push_back

const int maxn = 2e5+100;

//#define int ll
#define pii pair <int, int>
int inf = 1e9;

int color[maxn], used[maxn], timer, mt[maxn], p[maxn], a[maxn];

vector <int> edge[maxn];

void dfs(int v)
{
	for(auto to : edge[v])
	{
		if(color[to]) continue;
		color[to] = 3 - color[v];
		dfs(to);
	}
}

int kuhn(int v)
{
	if(used[v] == timer) return 0;
	used[v] = timer;
	for(auto to : edge[v])
	{
		if(mt[to] == -1 || kuhn(mt[to]))
		{
			mt[to] = v;
			return 1;
		}
	}
	return 0;
}

int findSample(int n,int confidence[],int host[],int protocol[])
{
	forn(1, i, n)
	{
		a[i] = confidence[i-1];
	}
	forn(2, i, n)
	{
		int par = host[i-1] + 1;
		if(protocol[i-1] == 0)
		{
			edge[par].pb(i);
			edge[i].pb(par);
		}
		else if(protocol[i-1] == 1)
		{
			for(auto to : edge[par])
			{
				edge[to].pb(i);
				edge[i].pb(to);
			}
		}
		else
		{
			for(auto to : edge[par])
			{
				edge[to].pb(i);
				edge[i].pb(to);
			}
			edge[par].pb(i);
			edge[i].pb(par);
		}
	}
/*	forn(1, i, n)
	{
		for(auto to : edge[i])
		{
			cout << i << " " << to << endl;
		}
	}*/
	forn(1, i, n)
	{
		mt[i] = -1;
		p[i] = -1;
		
	}
	forn(1, i, n)
	{
		p[i] = -1;
		if(color[i]) continue;
		color[i] = 1;
		dfs(i);
	}
	int run = 1;
	int ans = 0;
	while(run)
	{
		run = 0;
		timer++;
		forn(1, i, n)
		{
			if(color[i] == 1 && p[i] == -1 && kuhn(i))
			{
				p[i] = 1;
				ans++;
				run = 1;
			}
		}
	}
/*	cout << ans << endl;
	forn(1, i, n)
	{
		cout << p[i] << " " << mt[i] << " " << color[i] << endl;
	}*/
	return n - ans;
}
/*
// Confidence
int confidence[__MAXSIZE__];

// Host
int host[__MAXSIZE__];

// Protocol
int protocol[__MAXSIZE__];

// Main
int main(void)
{
	int n,i;

	// Number of people
	assert(scanf("%d",&n)==1);
	
	// Confidence
	for(i=0;i<n;i++)
		assert(scanf("%d",&confidence[i])==1);
	
	// Host and Protocol
	for(i=1;i<n;i++)
		assert(scanf("%d %d",&host[i],&protocol[i])==2);
	
	// Answer
	printf("%d\n",findSample(n,confidence,host,protocol));
	return 0;
}*/

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