Submission #872663

---

Source Code Expand

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
vector<int> gr[114514];
int pat[114514];
lint st[114514],go[114514],inp[114514];
bool sumi[114514];
int num[3];
int out=0,ng1=-1,ng2=-1;
vector<int> cycle;
int tmp[114514];
void dfs(int v,int p){
	if(pat[v]>=0) return;
	pat[v]=p;num[pat[v]]++;
	rep(i,gr[v].size()){
		int w=gr[v][i];
		if(v==ng1 && w==ng2) continue;
		if(v==ng2 && w==ng1) continue;
		dfs(w,1-p);
	}
}
void dfs2(int v,int u){
	rep(i,gr[v].size()){
		int w=gr[v][i];
		if(w==u) continue;
		if(v==ng1 && w==ng2) continue;
		if(v==ng2 && w==ng1) continue;
		dfs2(w,v);
		out+=abs(st[w]-go[w]);
		st[v]+=st[w];go[v]+=go[w];
	}
	if(pat[v]==1) st[v]++;else go[v]++;
}

lint cal(lint mi){
	memset(st,0,sizeof(st));
	memset(go,0,sizeof(go));
	st[ng1]=mi;go[ng2]=mi;out=0;
	dfs2(0,-1);
	return abs(mi)+out;
}

void dfscycle(int v,int u,int d){
	//cout<<v<<' '<<u<<' '<<d<<endl;
	if(sumi[v]){
		if(cycle.size()>0) return;
		int t=0;
		while(tmp[t]!=v && t<d) t++;
		//cout<<v<<' '<<t<<endl;
		REP(i,t,d) cycle.pb(tmp[i]);
		return;
	}
	tmp[d]=v;sumi[v]=true;
	rep(i,gr[v].size()){
		int w=gr[v][i];
		if(w==u) continue;
		dfscycle(w,v,d+1);
	}
	//sumi[v]=false;
	//tmp.pop_back();
}

int main()
{
	int n,m,a,b;
	scanf("%d %d",&n,&m);
	rep(i,m){
		scanf("%d %d",&a,&b);
		a--;b--;gr[a].pb(b);gr[b].pb(a);
	}
	if(n%2>0){
		cout<<-1<<endl;return 0;
	}
	memset(num,0,sizeof(num));
	memset(pat,-1,sizeof(pat));
	memset(st,0,sizeof(st));
	memset(go,0,sizeof(go));
	if(m==n-1){
		dfs(0,0);
		if(num[0]!=num[1]){
			cout<<-1<<endl;return 0;
		}
		dfs2(0,-1);
		cout<<out<<endl;
		return 0;
	}
	dfscycle(0,-1,0);
	ng1=cycle[0];ng2=cycle[1];
	//rep(i,cycle.size()) cout<<cycle[i]<<endl;
	if(cycle.size()%2==0){
		dfs(0,0);
		if(num[0]!=num[1]){
			cout<<-1<<endl;return 0;
		}
		int lo=-114514,hi=114514;lint out=1145141919810364364LL;
		while(hi>lo+5){
			lint m1=(lo+hi)/2,m2=m1+1,x1=cal(m1),x2=cal(m2);
			//cout<<m1<<' '<<x1<<' '<<m2<<' '<<x2<<endl;
			if(x1>x2) lo=m1;else hi=m2;
		}
		REP(i,lo,hi+1) out=min(out,cal(i));
		cout<<out<<endl;
		return 0;
	}
	dfs(ng1,0);pat[ng2]=0;
	if(num[0]>num[1]) st[ng1]=st[ng2]=(num[0]-num[1])/2;
	else go[ng1]=go[ng2]=(num[1]-num[0])/2;
	dfs2(0,-1);
	//cout<<num[0]<<' '<<num[1]<<endl;
	cout<<out+abs((num[0]-num[1])/2)<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:95:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
./Main.cpp:97:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);
                       ^

Judge Result