Submission #548877

#	Time	Username	Problem	Language	Result	Execution time	Memory
548877		CSQ31	Friend (IOI14_friend)	C++17	11 / 100	34 ms	4436 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<vector<int>> vii;
#define pb push_back
#define sz(a) (int)(a.size())
const ll INF = 1e18;
struct flowedge{
	int v,u;
	ll flow = 0,cap = 0;
	flowedge(int _v,int _u,ll _cap){
		v = _v;
		u = _u;
		cap = _cap;
	}
	
};
struct dinic{
	int n,m = 0,s,t;
	vector<flowedge>e;
	vector<int>ptr,level;
	vii adj;
	void add(int v,int u,ll cap){
		e.pb(flowedge(v,u,cap));
		e.pb(flowedge(u,v,0));
		adj[v].pb(m);
		adj[u].pb(++m);
		m++;
	}
	dinic(int _n,int _s,int _t){
		n = _n;
		adj.resize(n);
		ptr.assign(n,0);
		level.assign(n,-1);
		s = _s;
		t = _t;
	}
	void bfs(){
		queue<int>q;
		q.push(s);
		while(!q.empty()){
			int v = q.front();
			q.pop();
			for(int x:adj[v]){
				if(e[x].cap - e[x].flow && level[e[x].u] == -1){
					level[e[x].u] = level[v]+1;
					q.push(e[x].u);
				}
			}
		}
	}
	ll dfs(int v,ll f){
		if(!f)return 0;
		if(v == t)return f;
		for(;ptr[v]<sz(adj[v]);ptr[v]++){
			int i = adj[v][ptr[v]];
			if(e[i].cap - e[i].flow && level[e[i].u] == level[v] + 1){
				ll mn = dfs(e[i].u,min(f,e[i].cap - e[i].flow));
				//cout<<e[i].cap - e[i].flow<<" "<<mn<<'\n';
				if(!mn)continue;
				e[i].flow+=mn;
				e[i^1].flow-=mn;
				return mn;
			} 
		}
		return 0;
	}
	ll flow(){
		ll f = 0;
		while(true){
			for(int i=0;i<n;i++){
				ptr[i] = 0;
				level[i] = -1;
			}
			level[s] = 0;
			bfs();
			//for(int i=0;i<n;i++)cout<<level[i]<<" ";
			//cout<<'\n';
			if(level[t] == -1)break;
			while(true){
				ll x = dfs(s,INF);
				if(!x)break;
				f+=x;
			}
		}
		return f;
		
	}
};
int e[1000][1000],c[1000],N;
bool vis[1000];
bool check =1;
void dfs(int v){
	vis[v] = 1;
	for(int i=0;i<N;i++){
		if(e[v][i] && !vis[i]){
			c[i] = c[v]^1;
			dfs(i);
		}
		if(e[v][i] && vis[i] && c[i] == c[v])check = 0;
	}
	
}
int findSample(int n,int confidence[],int h[],int protocol[]){
	N=n;
	int ans = 0;
	bool sub4 = 1;
	for(int i=1;i<n;i++){
		if(protocol[i] == 2)sub4 = 0;
	}
	if(n<=10){
		vector<set<int>>adj(n);
		for(int i=1;i<n;i++){
			if(!protocol[i]){
				adj[i].insert(h[i]);
				adj[h[i]].insert(i);
			}else{
				for(int x:adj[h[i]]){
					adj[i].insert(x);
					adj[x].insert(i);
				}
			}
			if(protocol[i] == 2){
				adj[i].insert(h[i]);
				adj[h[i]].insert(i);
			}
		}
		for(int i=0;i<(1<<n);i++){
			vector<int>v;
			int cost = 0;
			for(int j=0;j<n;j++){
				if(i&(1<<j)){
					v.push_back(j);
					cost+=confidence[j];
				}
			}
			for(int x:v){
				for(int y:v){
					if(adj[x].count(y) || adj[y].count(x))cost = 0;
				}
			}
			ans = max(ans,cost);
		}
		return ans;
	}
	if(sub4){
		for(int i=1;i<n;i++){
			if(!protocol[i])e[i][h[i]] = e[h[i]][i] = 1;
			else{
				for(int j=0;j<n;j++){
					if(e[h[i]][j])e[i][j] = e[j][i] = 1;
				}
			}
		}
		dinic d(2*n+2,2*n,2*n+1);
		for(int i=0;i<n;i++){
			if(!vis[i])dfs(i);
		}
		assert(check);
		for(int i=0;i<n;i++){
			if(!c[i]){
				d.add(2*n,i,1);
				for(int j=0;j<n;j++){
					if(e[i][j])d.add(i,n+j,1);
				}
			}
			else d.add(n+i,2*n+1,1);
		}
		int ans = d.flow();
		return ans;
	}
	return 0;
}

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