Submission #385893

#	Time	Username	Problem	Language	Result	Execution time	Memory
385893		alireza_kaviani	Friend (IOI14_friend)	C++11	69 / 100	230 ms	65540 KiB

friend

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

#define all(x)		(x).begin() , (x).end()
#define SZ(x)		int(x.size())

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

struct MaxFlow{
	struct Edge{
		int from , to , flow , cap;
	};
	int s , t;
	vector<int> ptr , dist;
	vector<Edge> E;
	vector<vector<int>> adj;
	queue<int> Q;
	void init(int n){
		E.clear(); adj.clear(); ptr.clear(); dist.clear();
		adj.resize(n); ptr.resize(n); dist.resize(n);
	}
	void add(int v , int u , int cap){
		adj[v].push_back(SZ(E)); E.push_back({v , u , 0 , cap});
		adj[u].push_back(SZ(E)); E.push_back({u , v , 0 , 0});
	}
	int BFS(){
		fill(all(dist) , MOD);
		fill(all(ptr) , 0);
		dist[s] = 0;
		queue<int> q; q.push(s);
		while(!q.empty()){
			int v = q.front(); q.pop();
			for(int i : adj[v]){
				int u = E[i].to;
				if(E[i].flow == E[i].cap)	continue;
				if(dist[u] == MOD){
					dist[u] = dist[v] + 1;
					q.push(u);
				}
			}
		}
		return (dist[t] < MOD);
	}
	int DFS(int v , int w){
		if(v == t)	return w;
		int ans = 0;
		for( ; ptr[v] < SZ(adj[v]) ; ptr[v]++){
			int ind = adj[v][ptr[v]] , u = E[ind].to;
			if(E[ind].flow == E[ind].cap || dist[u] != dist[v] + 1)	continue;
			int cur = min(w - ans , E[ind].cap - E[ind].flow);
			int val = DFS(u , cur);
			ans += val; E[ind].flow += val; E[ind ^ 1].flow -= val;
			if(ans == w)	break;
		}
		return ans;
	}
	int flow(int v , int u){
		s = v; t = u; int ans = 0;
		while(BFS())	ans += DFS(s , MOD);
		return ans;
	}
} flow;

int col[MAXN];
vector<int> adj[MAXN];

int findSample(int n,int confidence[],int host[],int protocol[]){
	/*flow.init(10);
	flow.add(0 , 1 , 10);
	flow.add(0 , 2 , 10);
	flow.add(1 , 3 , 10);
	flow.add(2 , 3 , 7);
	flow.add(3 , 4 , 8);
	cout << flow.flow(0 , 4) << endl;*/
	int mx = 0 , sum = 0 , flag = 0;
	for(int i = 0 ; i < n ; i++){
		sum += confidence[i];
		mx = max(mx , confidence[i]);
	}
	for(int i = 1 ; i < n ; i++){
		protocol[i]++;
		if(protocol[i] & 2){
			for(int j : adj[host[i]]){
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
			col[i] = col[host[i]];
		}
		if(protocol[i] & 1){
			adj[i].push_back(host[i]);
			adj[host[i]].push_back(i);
			col[i] = (col[host[i]] ^ 1);
		}
		if(protocol[i] == 3){
			flag = 1;
		}
	}
	if(n <= 10){
		for(int i = 0 ; i < (1 << n) ; i++){
			int cur = 0 , fl = 0;
			for(int j = 0 ; j < n ; j++){
				if(i & (1 << j)){
					cur += confidence[j];
					for(int k : adj[j]){
						if(i & (1 << k))	fl = 1;
					}
				}
			}
			if(fl == 0)	mx = max(mx , cur);
		}
	}
	if(flag)	return mx;
	flow.init(n + 2);
	for(int i = 0 ; i < n ; i++){
		if(col[i] == 0){
			flow.add(0 , i + 1 , confidence[i]);
			for(int j : adj[i])	flow.add(i + 1 , j + 1 , MOD);
		}
		else	flow.add(i + 1 , n + 1 , confidence[i]);
	}
	return sum - flow.flow(0 , n + 1);
}

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