Submission #382530


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)<<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 0
Code Size 1858 Byte
Status WA
Exec Time 676 ms
Memory 49112 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 40 0 / 70
Status
AC × 2
AC × 15
WA × 5
AC × 21
WA × 12
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 82 ms 18716 KB
sample_02.txt AC 81 ms 18728 KB
subtask1_01.txt AC 82 ms 18720 KB
subtask1_02.txt AC 83 ms 18716 KB
subtask1_03.txt AC 66 ms 18784 KB
subtask1_04.txt WA 69 ms 18788 KB
subtask1_05.txt WA 70 ms 18764 KB
subtask1_06.txt WA 70 ms 18784 KB
subtask1_07.txt AC 65 ms 18780 KB
subtask1_08.txt AC 69 ms 18788 KB
subtask1_09.txt WA 65 ms 18776 KB
subtask1_10.txt AC 67 ms 18780 KB
subtask1_11.txt AC 65 ms 18784 KB
subtask1_12.txt AC 63 ms 18776 KB
subtask1_13.txt AC 65 ms 18776 KB
subtask1_14.txt AC 65 ms 18780 KB
subtask1_15.txt AC 64 ms 18776 KB
subtask1_16.txt WA 66 ms 18784 KB
subtask1_17.txt AC 69 ms 18780 KB
subtask1_18.txt AC 69 ms 18776 KB
subtask2_01.txt WA 663 ms 38500 KB
subtask2_02.txt WA 667 ms 38732 KB
subtask2_03.txt WA 552 ms 39280 KB
subtask2_04.txt WA 657 ms 37800 KB
subtask2_05.txt AC 581 ms 37844 KB
subtask2_06.txt AC 595 ms 38104 KB
subtask2_07.txt AC 426 ms 37284 KB
subtask2_08.txt AC 676 ms 49112 KB
subtask2_09.txt WA 628 ms 38880 KB
subtask2_10.txt AC 164 ms 23128 KB
subtask2_11.txt AC 180 ms 21460 KB
subtask2_12.txt WA 470 ms 31776 KB
subtask2_13.txt AC 552 ms 35032 KB
subtask2_14.txt WA 580 ms 37848 KB
subtask2_15.txt AC 227 ms 22548 KB