Submission #292693

#	Time	Username	Problem	Language	Result	Execution time	Memory
292693		TMJN	Friend (IOI14_friend)	C++17	69 / 100	39 ms	2808 KiB

friend

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

int solve_1(int n,int confidence[],int host[],int protocol[]){
	vector<int>v[10];
	for(int i=1;i<n;i++){
		if(protocol[i]==0){
			v[i].push_back(host[i]);
			v[host[i]].push_back(i);
		}
		if(protocol[i]==1){
			for(int j:v[host[i]]){
				v[j].push_back(i);
				v[i].push_back(j);
			}
		}
		if(protocol[i]==2){
			for(int j:v[host[i]]){
				v[j].push_back(i);
				v[i].push_back(j);
			}
			v[i].push_back(host[i]);
			v[host[i]].push_back(i);
		}
	}
	int res=0;
	for(int i=0;i<(1<<n);i++){
		bool b[10];
		for(int j=0;j<n;j++){
			b[j]=(i>>j)&1;
		}
		bool f=true;
		int c=0;
		for(int j=0;j<n;j++){
			if(!b[j])continue;
			c+=confidence[j];
			for(int k:v[j]){
				if(b[k])f=false;
			}
		}
		if(f&&res<c)res=c;
	}
	return res;
}

int solve_2(int n,int confidence[],int host[],int protocol[]){
	int res=0;
	for(int i=0;i<n;i++){
		res+=confidence[i];
	}
	return res;
}

int solve_3(int n,int confidence[],int host[],int protocol[]){
	int res=0;
	for(int i=0;i<n;i++){
		if(res<confidence[i])res=confidence[i];
	}
	return res;
}

vector<int>v_4[1000];
int C_4[1000][2];

void dfs_4(int x,int from){
	for(int i:v_4[x]){
		if(i==from)continue;
		dfs_4(i,x);
		C_4[x][0]+=max(C_4[i][0],C_4[i][1]);
		C_4[x][1]+=C_4[i][0];
	}
}

int solve_4(int n,int confidence[],int host[],int protocol[]){
	for(int i=1;i<n;i++){
		v_4[i].push_back(host[i]);
		v_4[host[i]].push_back(i);
	}
	for(int i=0;i<n;i++){
		C_4[i][1]=confidence[i];
	}
	dfs_4(0,0);
	return max(C_4[0][0],C_4[0][1]);
}

struct edge{
	int to,cost,rev;
};

vector<edge>e_5[1002];
vector<int>v_5[1000];
bool vis_5[1002],bw_5[1000];

void init_5(){
	for(int i=0;i<1002;i++){
		e_5[i].clear();
		vis_5[i]=false;
	}
	for(int i=0;i<1000;i++){
		v_5[i].clear();
		bw_5[i]=false;
	}
}

void dfs_5(int x){
	vis_5[x]=true;
	for(int i:v_5[x]){
		if(vis_5[i])continue;
		bw_5[i]=bw_5[x]^true;
		dfs_5(i);
	}
}

int dfs2_5(int n,int x,int cost){
	if(x==n+1)return cost;
	vis_5[x]=true;
	for(edge &e:e_5[x]){
		if(!vis_5[e.to]&&e.cost){
			int k=dfs2_5(n,e.to,min(cost,e.cost));
			if(k){
				e.cost-=k;
				e_5[e.to][e.rev].cost+=k;
				return k;
			}
		}
	}
	return 0;
}

int calc_max_flow_5(int n){
	int c=0;
	while(true){
		for(int i=0;i<n+2;i++){
			vis_5[i]=false;
		}
		int k=dfs2_5(n,n,0xE869120);
		if(!k)break;
		c+=k;
	}
	return c;
}

int solve_5(int n,int confidence[],int host[],int protocol[]){
	for(int i=1;i<n;i++){
		if(protocol[i]==0){
			v_5[i].push_back(host[i]);
			v_5[host[i]].push_back(i);
		}
		if(protocol[i]==1){
			for(int j:v_5[host[i]]){
				v_5[j].push_back(i);
				v_5[i].push_back(j);
			}
		}
	}
	for(int i=0;i<n;i++){
		if(!vis_5[i]){
			dfs_5(i);
		}
	}
	for(int i=0;i<n;i++){
		if(bw_5[i]){
			e_5[n].push_back({i,1,e_5[i].size()});
			e_5[i].push_back({n,0,e_5[n].size()-1});
			for(int j:v_5[i]){
				e_5[i].push_back({j,0xE869120,e_5[j].size()});
				e_5[j].push_back({i,0,e_5[i].size()-1});
			}
		}
		else{
			e_5[i].push_back({n+1,1,e_5[n+1].size()});
			e_5[n+1].push_back({i,0,e_5[i].size()-1});
		}
	}
	return n-calc_max_flow_5(n);
}


int findSample(int n,int confidence[],int host[],int protocol[]){
	if(n<=10){
		return solve_1(n,confidence,host,protocol);
	}
	bool used[3],f;
	for(int i=0;i<3;i++)used[i]=false;
	f=true;
	for(int i=1;i<n;i++){
		if(confidence[i]!=1)f=false;
		used[protocol[i]]=true;
	}
	if(!used[0]&&used[1]&&!used[2]){
		return solve_2(n,confidence,host,protocol);
	}
	if(!used[0]&&!used[1]&&used[2]){
		return solve_3(n,confidence,host,protocol);
	}
	if(used[0]&&!used[1]&&!used[2]){
		return solve_4(n,confidence,host,protocol);
	}
	if(f&&!used[2]){
		return solve_5(n,confidence,host,protocol);
	}
	return -1;
}

Compilation message (stderr)

friend.cpp: In function 'int solve_5(int, int*, int*, int*)':
friend.cpp:164:37: warning: narrowing conversion of 'e_5[i].std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  164 |    e_5[n].push_back({i,1,e_5[i].size()});
      |                          ~~~~~~~~~~~^~
friend.cpp:165:39: warning: narrowing conversion of '(e_5[n].std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  165 |    e_5[i].push_back({n,0,e_5[n].size()-1});
      |                          ~~~~~~~~~~~~~^~
friend.cpp:167:46: warning: narrowing conversion of 'e_5[j].std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  167 |     e_5[i].push_back({j,0xE869120,e_5[j].size()});
      |                                   ~~~~~~~~~~~^~
friend.cpp:168:40: warning: narrowing conversion of '(e_5[i].std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  168 |     e_5[j].push_back({i,0,e_5[i].size()-1});
      |                           ~~~~~~~~~~~~~^~
friend.cpp:172:41: warning: narrowing conversion of 'e_5[(n + 1)].std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  172 |    e_5[i].push_back({n+1,1,e_5[n+1].size()});
      |                            ~~~~~~~~~~~~~^~
friend.cpp:173:41: warning: narrowing conversion of '(e_5[i].std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  173 |    e_5[n+1].push_back({i,0,e_5[i].size()-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