Submission #764698

#	Time	Username	Problem	Language	Result	Execution time	Memory
764698		pere_gil	Logičari (COCI21_logicari)	C++14	0 / 110	765 ms	524288 KiB

Main

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

const int MAX_N=1e3+5;
vector<int> adj[MAX_N];
bool in[MAX_N];
int a,b,col_a,col_b;
int space=4;

void pri(int n){
	if(!n) return;
	string s(n,' '); s[n-1]='|';
	printf("%s",s.c_str());
}

void find_cycle(int u){
	if(adj[u].size()>2) return;
	in[u]=false;
	for(int v: adj[u])
		if(in[v]) find_cycle(v);
}

// 0: !blue | 1: blue
int f(int u, int col, int pa, int col_pa, int prof){
	if(col_pa && u==b && col_a) return -1;
	if((u==a && col!=col_a) || (u==b && col!=col_b)) return -1;

	bool cov=col_pa||(u==a && col_b)||(u==b && col_a);

	if(cov){
		vector<pair<int,int>> aux;
		bool sw=false;
		int sum=0;
		for(int v: adj[u]) if(v!=pa){
				int act=f(v,0,u,col,prof);
				sum+=act;
				sw|=act==-1;
				
				aux.push_back({v,act});
			}

		//printf("--------------------\n\n");
		//printf("%d %c | %d %c\n",u,col,pa,col_pa);
		//for(auto x: aux) printf("%d -> %d\n",x.first,x.second);
		//if(sw) printf("not all can white so NO\n");
		return sw ? -1 : sum;
	}
	else{
		vector<pair<int,pair<int,int>>> aux;
		int sum=0,cont=0,bad;
		for(int i=0;i<adj[u].size();i++) if(adj[u][i]!=pa){
				int v=adj[u][i];
				int act=f(v,0,u,col,prof);
				aux.push_back({v,{act,0}});
				if(act==-1){
					cont++;
					bad=aux.size()-1;
				}
				else sum+=act;

				act=f(v,1,u,col,prof);
				aux.back().second.second=act;
			}

		//printf("--------------------\n\n");
		//printf("%d %c | %d %c\n",u,col,pa,col_pa);
		//for(auto x: aux) printf("%d -> %d ; %d\n",x.first,x.second.first,x.second.second);
		if(cont>1){
			//printf("more than 1 can't white\n");
			return -1;
		}
		if(cont==1){
			//printf("just one can't white: %d\n",aux[bad].first+1);
			if(aux[bad].second.second==-1){
				//printf("can't blue so -1\n");
				return -1;
			}
			else{
				//printf("can blue so %d\n",sum+aux[bad].second.second+1);
				return sum+aux[bad].second.second+1;
			}
		}

		int res=1e9;
		for(int i=0;i<aux.size();i++){
			if(aux[i].second.second==-1){
				//printf("%d can't blue\n",aux[i].first);
				continue;
			}
			//printf("%d blue\n",aux[i].first);
			//printf("cost: %d\n",sum-aux[i].second.first+aux[i].second.second+1);
			res=min(res,sum-aux[i].second.first+aux[i].second.second+1);
		}

		if(res==1e9){
			//printf("no one can be blue so -1\n");
			return -1;
		}
		else return res;
	}
	
	return -1;
}

int main(){
	int n; scanf("%d",&n);
	vector<pair<int,int>> con(n);
	for(int i=0;i<n;i++){
		int u,v; scanf("%d %d",&u,&v);
		u--,v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
		con[i]={u,v};
	}
	
	memset(in,true,sizeof in);
	for(int i=0;i<n;i++)
		if(adj[i].size()==1) find_cycle(i);

	int res=1e9;
	for(int i=0;i<n;i++){
		a=con[i].first,b=con[i].second;
		if(!in[a] || !in[b]) continue;

		vector<int> prev_a=adj[a],prev_b=adj[b],aux_a,aux_b;
		for(int x: adj[a])
			if(x!=b) aux_a.push_back(x);
		for(int x: adj[b])
			if(x!=a) aux_b.push_back(x);
		adj[a]=aux_a,adj[b]=aux_b;
		
		for(col_a=0;col_a<2;col_a++)
			for(col_b=0;col_b<2;col_b++){
				//printf("------------------------------\n");
				int act=f(a,col_a,-1,0,0);
				//printf("ans: %d\n--------------------\n",act+col_a+col_b);
				if(act!=-1) res=min(res,act+col_a+col_b);
			}
		
		adj[a]=prev_a,adj[b]=prev_b;
	}

	printf("%d\n",res==1e9 ? -1 : res);
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int f(int, int, int, int, int)':
Main.cpp:51:16: 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<adj[u].size();i++) if(adj[u][i]!=pa){
      |               ~^~~~~~~~~~~~~~
Main.cpp:85:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i=0;i<aux.size();i++){
      |               ~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  int n; scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:109:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |   int u,v; scanf("%d %d",&u,&v);
      |            ~~~~~^~~~~~~~~~~~~~~
Main.cpp: In function 'int f(int, int, int, int, int)':
Main.cpp:74:14: warning: 'bad' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |    if(aux[bad].second.second==-1){
      |              ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50