#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
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){
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
2004 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
765 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
765 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
2004 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
