Submission #1674182


Source Code Expand

#include<bits/stdc++.h> 
#define N 100005
using namespace std;
struct edge{
	int t,next;
}e[N*2];int ecnt,head[N];
void addedge(int f,int t){
	e[++ecnt]=(edge){t,head[f]};head[f]=ecnt;
	e[++ecnt]=(edge){f,head[t]};head[t]=ecnt;
}
long long ans;
int ini[N],ax[N],delta[N],del;
void DFS(int u,int fr){
	delta[u]=ini[u];
	for(int i=head[u];i;i=e[i].next){
		if(e[i].t!=fr&&i!=del&&i!=(del^1)){
			DFS(e[i].t,u);
			delta[u]-=delta[e[i].t];
			ax[u]-=ax[e[i].t];
		}
	}
	ax[u]==0? ans+=abs(delta[u]):0;
}
int vis[N],num[2],A,B,type[N];
void DFS2(int u,int fr,int side){//find the circle
	num[side]++;vis[u]=1;type[u]=side;
	for(int i=head[u];i;i=e[i].next){
		if(e[i].t==fr) continue;
		if(vis[e[i].t]==0){
			DFS2(e[i].t,u,side^1);
		}else{
			A=u;B=e[i].t;del=i;
		}
	}
}
int n,m;
void solve1(){
	del=0;
	DFS(1,0);
	if(delta[1]!=0) puts("-1"),exit(0);
}
void solve2(){
	DFS2(1,0,0);
	if(type[A]==type[B]){//odd
		int t=(num[type[A]^1]-num[type[A]])/2;
		ini[A]+=t;ini[B]+=t;
		DFS(A,0);
		ans+=abs(t);
	}else{//even
		if(num[0]!=num[1]) puts("-1"),exit(0);
		ax[B]=-1;
		DFS(A,0);
		assert(ax[A]==1);
		assert(delta[A]==0);
		vector<int> v;
		for(int i=1;i<=n;i++) 
			if(ax[i]!=0)
				v.push_back(-ax[i]*delta[i]);
		sort(v.begin(),v.end());
		for(int i=0,mid=v[v.size()/2];i<v.size();i++) ans+=abs(mid-v[i]);
	}
}
int main(){
	scanf("%d%d",&n,&m);ecnt=1;
	if(n%2!=0) return puts("-1"),0; 
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),addedge(u,v);
	for(int i=1;i<=n;i++) ini[i]+=1;
	if(m==n-1) solve1();
	else solve2();
	cout<<ans<<endl;
	return 0;
}

Submission Info

Submission Time
Task F - Namori
User Wuvin
Language C++14 (GCC 5.4.1)
Score 2200
Code Size 1623 Byte
Status AC
Exec Time 41 ms
Memory 9468 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:64:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);ecnt=1;
                     ^
./Main.cpp:66:60: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),addedge(u,v);
                                                            ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 1500 / 1500 700 / 700
Status
AC × 4
AC × 20
AC × 66
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
Subtask1 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 29 ms 7936 KB
1_02.txt AC 25 ms 4608 KB
1_03.txt AC 21 ms 2944 KB
1_04.txt AC 27 ms 5376 KB
1_05.txt AC 27 ms 5248 KB
1_06.txt AC 27 ms 5248 KB
1_07.txt AC 26 ms 4736 KB
1_08.txt AC 27 ms 5632 KB
1_09.txt AC 23 ms 3328 KB
1_10.txt AC 24 ms 3328 KB
1_11.txt AC 24 ms 3328 KB
1_12.txt AC 25 ms 3328 KB
1_13.txt AC 1 ms 256 KB
1_14.txt AC 25 ms 3456 KB
1_15.txt AC 25 ms 3328 KB
1_16.txt AC 1 ms 256 KB
1_17.txt AC 25 ms 3328 KB
2_00.txt AC 1 ms 256 KB
2_01.txt AC 41 ms 9468 KB
2_02.txt AC 33 ms 6912 KB
2_03.txt AC 24 ms 3840 KB
2_04.txt AC 35 ms 6912 KB
2_05.txt AC 37 ms 6912 KB
2_06.txt AC 35 ms 6912 KB
2_07.txt AC 37 ms 6912 KB
2_08.txt AC 37 ms 6912 KB
2_09.txt AC 26 ms 4096 KB
2_10.txt AC 28 ms 4096 KB
2_11.txt AC 30 ms 4096 KB
2_12.txt AC 29 ms 4096 KB
2_13.txt AC 1 ms 256 KB
2_14.txt AC 24 ms 3584 KB
2_15.txt AC 29 ms 4224 KB
2_16.txt AC 1 ms 256 KB
2_17.txt AC 29 ms 4224 KB
2_18.txt AC 1 ms 256 KB
2_19.txt AC 29 ms 6528 KB
2_20.txt AC 23 ms 3712 KB
2_21.txt AC 38 ms 9468 KB
2_22.txt AC 31 ms 6528 KB
2_23.txt AC 32 ms 6528 KB
2_24.txt AC 33 ms 6528 KB
2_25.txt AC 31 ms 6528 KB
2_26.txt AC 32 ms 6528 KB
2_27.txt AC 27 ms 4096 KB
2_28.txt AC 28 ms 4096 KB
2_29.txt AC 29 ms 4096 KB
2_30.txt AC 29 ms 4096 KB
2_31.txt AC 1 ms 256 KB
2_32.txt AC 29 ms 4352 KB
2_33.txt AC 30 ms 4224 KB
2_34.txt AC 1 ms 256 KB
2_35.txt AC 29 ms 4096 KB
2_36.txt AC 23 ms 3840 KB
2_37.txt AC 23 ms 3840 KB
2_38.txt AC 23 ms 3712 KB
2_39.txt AC 23 ms 3840 KB
2_40.txt AC 23 ms 3840 KB
2_41.txt AC 23 ms 3840 KB
2_42.txt AC 23 ms 3840 KB
2_43.txt AC 23 ms 3712 KB