Submission #872003

---

Source Code Expand

#include<bits/stdc++.h>
#define N 100100
using namespace std;
vector<int> g[N];
int deg[N],val[N],tv[N];
int id[N],cnt;
bool del[N];
int main(){
	long long ans=0;
	int n,m,x,y;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
		deg[x]++;
		deg[y]++;
	}
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(deg[i]==1) q.push(i);
		val[i]=1;
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(deg[u]!=1){
			continue;
		}
		del[u]=true;
		ans+=abs(val[u]);
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(del[v]) continue;
			val[v]-=val[u];
			if(--deg[v]==1) q.push(v);
		}
	}
	for(int i=1;i<=n;i++){
		if(!del[i]){
			while(1){
				del[i]=true;
				id[cnt++]=i;
				int nxt=-1;
				for(int j=0;j<g[i].size();j++){
					if(del[g[i][j]]) continue;
					nxt=g[i][j];
					break;
				}
				if(nxt<0) break;
				i=nxt;
			}
			break;
		}
	}
	if(cnt==1){
		if(val[id[0]]) puts("-1");
		else printf("%lld\n",ans);
	}
	else if(cnt&1){
		long long tmp=0;
		for(int i=0;i<cnt;i++){
			tmp+=val[id[i]];
		}
		if(tmp&1) puts("-1");
		else{
			tmp>>=1;
			for(int i=1;i<cnt;i+=2){
				tmp-=val[id[i]];
			}
			for(int i=0;i<cnt;i++){
				ans+=abs(tmp);
				tmp=val[id[i]]-tmp;
			}
			printf("%lld\n",ans);
		}
	}
	else{
		long long tmp=0;
		for(int i=0;i<cnt;i++){
			if(i&1) tv[i]=-tmp;
			else tv[i]=tmp;
			tmp=val[id[i]]-tmp;
		}
		if(tmp) puts("-1");
		else{
			sort(tv,tv+cnt);
			for(int i=0;i<cnt-1-i;i++){
				ans+=tv[cnt-1-i]-tv[i];
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

Submission Info

Compile Error

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

Judge Result