Submission #337977

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b)  FOR(i,0,b)
#define X first
#define Y second
#define S second
#define F first
#define PB(a) push_back(a)
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pr;
typedef pair<LL,pr> ppr;
typedef priority_queue<ppr,vector<ppr>,greater<ppr> > PQ;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef vector<int> VI;
const int INF=1<<30;
const int SIZE=500001;
const LL p=(1e+9)+7;
int unions[SIZE];
LL twin[SIZE+1];
bool need[SIZE];
Vpr edges;
Vpr edge[SIZE];
int reached[SIZE];
LL twins(int x){
	if(twin[x]) return twin[x];
	if(x==0) return 1;
	if(x==1) return 2;
	return twin[x]=(twins(x/2)*twins((x+1)/2))%p;
}
int find(int x){
	if(x==unions[x]) return x;
	return unions[x]=find(unions[x]);
}
void unit(int a,int b){
	a=find(a);
	b=find(b);
	unions[max(a,b)]=min(a,b);
}
bool isfriend(int a,int b){
	return find(a)==find(b);
}
int main(){
	int N,M,c,a,b;
	LL x,y;
	LL ans=0;
	
	cin >> N >> M;
	REP(i,SIZE)
		unions[i]=i;
	REP(i,M){
		scanf("%d%d",&a,&b);
		if(!isfriend(a,b)){
			unit(a,b);
			edge[a].PB(pr(b,i+1));
			edge[b].PB(pr(a,i+1));
		}
		edges.PB(pr(a,b));
		need[a]^=1;
		need[b]^=1;
		ans=(ans+twins(i+1))%p;
	}
	queue<int> qu;
	FOR(i,1,N+1){
		if(edge[i].size()==1){
			qu.push(i);

		}

	}
	while(!qu.empty()){
		int now=qu.front();
		reached[now]++;
		REP(i,edge[now].size()){
			int next=edge[now][i].F;
			int cost=edge[now][i].S;
			if(reached[next]==edge[next].size()) continue;
			if(need[now]){
				ans=(ans+twins(cost))%p;
				need[next]^=1;
			}
			reached[next]++;
			if(reached[next]+1==edge[next].size()) qu.push(next);
		}
		qu.pop();
	}
	cout << ans << endl;


}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:54:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result