#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;
}
Compilation message
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);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
224 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
2004 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
224 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
2004 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
