Submission #382531


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<to;x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

int N,M;

ll p2[505050];
int odd[505050];
vector<pair<int,int> > E[505000];
ll mo=1000000007;
ll ret;

ll dfs(int cur,int pre) {
	ll ret=0;
	FORR(r,E[cur]) if(r.first!=pre) {
		ret += dfs(r.first,cur);
		if(odd[r.first]==0) ret += r.second;
		odd[cur]^=odd[r.first];
	}
	return ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	UF<500000> uf;
	
	cin>>N>>M;
	
	p2[0]=1;
	FOR(i,M) {
		p2[i+1]=p2[i]*2%mo;
		cin>>x>>y;
		x--,y--;
		ret = (ret+p2[i+1])%mo;
		if(uf[x]==uf[y]) {
			odd[x]^=1;
			odd[y]^=1;
		}
		else {
			uf(x,y);
			E[x].emplace_back(y,p2[i+1]);
			E[y].emplace_back(x,p2[i+1]);
		}
	}
	cout<<(ret+dfs(0,-1))%mo<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}

Submission Info

Submission Time
Task C - ドライブ
User kmjp
Language C++11 (GCC 4.8.1)
Score 110
Code Size 1863 Byte
Status AC
Exec Time 672 ms
Memory 49092 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 40 / 40 70 / 70
Status
AC × 2
AC × 20
AC × 33
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt
Subtask2 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt
Case Name Status Exec Time Memory
sample_01.txt AC 81 ms 18804 KB
sample_02.txt AC 73 ms 18784 KB
subtask1_01.txt AC 77 ms 18720 KB
subtask1_02.txt AC 63 ms 18788 KB
subtask1_03.txt AC 63 ms 18788 KB
subtask1_04.txt AC 67 ms 18784 KB
subtask1_05.txt AC 68 ms 18788 KB
subtask1_06.txt AC 68 ms 18780 KB
subtask1_07.txt AC 68 ms 18796 KB
subtask1_08.txt AC 69 ms 18776 KB
subtask1_09.txt AC 68 ms 18780 KB
subtask1_10.txt AC 68 ms 18792 KB
subtask1_11.txt AC 68 ms 18792 KB
subtask1_12.txt AC 65 ms 18764 KB
subtask1_13.txt AC 68 ms 18844 KB
subtask1_14.txt AC 68 ms 18788 KB
subtask1_15.txt AC 69 ms 18784 KB
subtask1_16.txt AC 70 ms 18776 KB
subtask1_17.txt AC 67 ms 18784 KB
subtask1_18.txt AC 70 ms 18716 KB
subtask2_01.txt AC 659 ms 38508 KB
subtask2_02.txt AC 672 ms 38712 KB
subtask2_03.txt AC 536 ms 39260 KB
subtask2_04.txt AC 655 ms 37856 KB
subtask2_05.txt AC 581 ms 37848 KB
subtask2_06.txt AC 574 ms 38104 KB
subtask2_07.txt AC 404 ms 37280 KB
subtask2_08.txt AC 627 ms 49092 KB
subtask2_09.txt AC 663 ms 38904 KB
subtask2_10.txt AC 168 ms 23132 KB
subtask2_11.txt AC 187 ms 21436 KB
subtask2_12.txt AC 454 ms 31832 KB
subtask2_13.txt AC 535 ms 35036 KB
subtask2_14.txt AC 572 ms 37768 KB
subtask2_15.txt AC 222 ms 22612 KB