Submission #1040901

---

Source Code Expand

#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<lint,lint> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;
int n,m;
vector<int> g[100005];
void ng(){
  puts("-1");
  exit(0);
}
pi dfs(int v,int p){
  int cost=0,flip=0;
  for(auto to:g[v]){
    if(to==p) continue;
    pi nxt=dfs(to,v);
    cost+=nxt.fr;
    flip+=nxt.sc;
  }
  if(flip==1) return mp(cost,0);
  else return mp(cost+abs(flip-1),1-flip);
}

void solve1(){
  REP(i,n-1){
    int a,b;scanf("%d%d",&a,&b);--a;--b;
    g[a].pb(b);
    g[b].pb(a);
  }
  pi res=dfs(0,-1);
  if(res.sc) ng();
  printf("%lld\n",res.fr);
}


struct uf{

  static const int MAXN=100005;
  int par[MAXN];
  int size[MAXN];
  void init(){
    memset(par,-1,sizeof(par));
    REP(i,MAXN) size[i]=1;
  }
  int root(int a){
    if(par[a]==-1) return a;
    return par[a]=root(par[a]);
  }
  void unite(int a,int b){
    a=root(a);b=root(b);
    if(a==b) return;
    if(size[a]<size[b]) swap(a,b);

    par[b]=a;
    size[a]+=size[b];
  }
  bool same(int a,int b){
    return root(a)==root(b);
  }
};
uf u;

vector<int> path,ever;
bool inCycle[100005];
void findpath(int a,int p,int b){
  ever.pb(a);
  if(a==b){
    path=ever;
  }
  for(auto to:g[a]){
    if(to==p) continue;
    findpath(to,a,b);
  }
  ever.pop_back();
}
pi dfs2(int v,int p){
  int cost=0,flip=0;
  for(auto to:g[v]){
    if(to==p || inCycle[to]) continue;
    pi nxt=dfs2(to,v);
    cost+=nxt.fr;
    flip+=nxt.sc;
  }
  if(flip==1) return mp(cost,0);
  else return mp(cost+abs(flip-1),1-flip);
}
pi es[100005];

void massert(bool a){
  if(!a) while(1){};
}

void solve2(){
  u.init();
  REP(i,m){
    int a,b;scanf("%d%d",&a,&b);--a;--b;
    es[i]=mp(a,b);
    if(u.same(a,b)){
      findpath(a,-1,b);
    }else{
      u.unite(a,b);
      g[a].pb(b);
      g[b].pb(a);
    }
  }
  debug(ALL(path));
  for(auto e:path) inCycle[e]=1;

  REP(i,n) g[i].clear();

  REP(i,m){
    int a=es[i].fr,b=es[i].sc;
    if(!inCycle[a] || !inCycle[b]){
      g[a].pb(b);
      g[b].pb(a);
    }
  }

  lint res=0,sum=0;
  vector<lint> ar(path.size());
  REP(i,path.size()){
    int v=path[i];
    pi nxt=dfs2(v,-1);
    dump(nxt);
    nxt.fr-=abs(nxt.sc);
    res+=nxt.fr;
    ar[i]=nxt.sc;
    sum+=ar[i];
  }
  if(sum&1) ng();
  dump(res);

  int n2=ar.size();
  vector<lint> prev=ar;
  debug(ALL(ar));
  REP(i,n2-1){
    ar[i+1]-=ar[i];
  }
  res+=abs(ar[n2-1])/2;
  if(ar[n2-1]!=0 && n2%2==0) ng();

  if(n2&1){
    debug(ALL(ar));
    prev[0]-=ar[n2-1]/2;
    prev[n2-1]-=ar[n2-1]/2;
    ar=prev;
    debug(ALL(prev));
    REP(i,n2-1){
      ar[i+1]-=ar[i];
      res+=abs(ar[i]);
      dump(res);
    }
  }else{
    ar=prev;
    pi val=mp(1,ar[0]);
    vector<lint> pivs;pivs.pb(0);
    REP(i,n2-1){
      dump(val);
      pivs.pb(-val.sc*val.fr);
      pi nxt=mp(-val.fr,ar[i+1]-val.sc);
      val=nxt;
    }
    dump(val);
    sort(ALL(pivs));
    debug(ALL(pivs));
    lint v=pivs[n2/2];
    REP(i,n2) res+=abs(pivs[i]-v);
  }
  cout<<res<<endl;
}

int main(){
  cin>>n>>m;
  if(n&1) ng();
  if(m==n-1) solve1();
  else solve2();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve1()’:
./Main.cpp:66:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int a,b;scanf("%d%d",&a,&b);--a;--b;
                                ^
./Main.cpp: In function ‘void solve2()’:
./Main.cpp:136:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int a,b;scanf("%d%d",&a,&b);--a;--b;
                                ^

Judge Result