제출 #764696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764696		pere_gil	Logičari (COCI21_logicari)	C++14	0 / 110	2 ms	2004 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){
	//pri(prof); printf("state: %d %d | %d %d\n",u+1,col,pa+1,col_pa);
	
	if(col_pa && u==b && col_a){
		//printf("-1 2 blue\n");
		//pri(prof); printf("--------------------\n");
		return -1;
	}
	if((u==a && col!=col_a) || (u==b && col!=col_b)){
		//printf("-1 impossible\n");
		//pri(prof); printf("--------------------\n");
		return -1;
	}

	bool cov=col_pa||(u==a && col_b)||(u==b && col_a);
	
	if(cov){
		//pri(prof); printf("cov\n");
		int res=0;
		bool sw=false;
		for(int v: adj[u])
			if(v!=pa){
				int act=f(v,0,u,col,prof+space);
				res+=act;
				sw|=act==-1;
			}
		if(sw){
			//pri(prof); printf("not all can white\n");
		}
		else{
			//pri(prof); printf("all can white: %d\n",res);
		}
		//pri(prof); printf("--------------------\n");
		return sw ? -1 : res;
	}
	else{
		//pri(prof); printf("not cov\n");
		int res=1e9,sum=0;
		vector<int> val;
		int cont=0,bad=0;
		int ind=0;
		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+space);
				val.push_back(act);
				
				if(act==-1){
					bad=i;
					cont++;
				}
				else sum+=act;
			}
		//printf("\n");

		if(cont>1){
			//pri(prof); printf("more than one can't white\n");
			//pri(prof); printf("--------------------\n");
			return -1;
		}
		if(cont){
			//pri(prof); printf("one can't white: %d\n",adj[u][bad]+1);
			int v=adj[u][bad];
			int act=f(v,1,u,col,prof+space);
			if(act==-1){
				//pri(prof); printf("can't blue so dead\n");
			}
			else{
				//pri(prof); printf("can so %d\n",sum+act);
			}
			//pri(prof); printf("--------------------\n");
			return act==-1 ? -1 : sum+act+1;
		}

		ind=0;
		//pri(prof); printf("sum: %d\n",sum);
		for(int i=0;i<adj[u].size();i++) if(adj[u][i]!=pa){
				int v=adj[u][i];
				//pri(prof); printf("%d: %d\n",v+1,val[ind++]);
			}

		ind=0;
		for(int i=0;i<adj[u].size();i++) if(adj[u][i]!=pa){
				int v=adj[u][i];

				int act=f(v,1,u,col,prof+space);
				if(act==-1) continue;
				res=min(res,sum-val[ind++]+act+1);
			}
		if(res==1e9){
			//pri(prof); printf("no one can blue\n");
		}
		else{
			//pri(prof); printf("at least one can blue, %d\n",res);
		}
		return res==1e9 ? -1 : 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;

		//printf("rem: %d ; %d\n",a+1,b+1);

		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++){
				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;

		break;
	}

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

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int f(int, int, int, int, int)':
Main.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<adj[u].size();i++) if(adj[u][i]!=pa){
      |               ~^~~~~~~~~~~~~~
Main.cpp:99:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int i=0;i<adj[u].size();i++) if(adj[u][i]!=pa){
      |               ~^~~~~~~~~~~~~~
Main.cpp:100:9: warning: unused variable 'v' [-Wunused-variable]
  100 |     int v=adj[u][i];
      |         ^
Main.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int i=0;i<adj[u].size();i++) if(adj[u][i]!=pa){
      |               ~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  int n; scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:127:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |   int u,v; scanf("%d %d",&u,&v);
      |            ~~~~~^~~~~~~~~~~~~~~

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