Submission #338106
Source Code Expand
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <utility>
#include <complex>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
int par[400000];
void init(int n){rep(i,n) par[i]=i;}
int find(int x){
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
bool same(int x,int y){
return find(x)==find(y);
}
void unite(int x,int y){
x=find(x),y=find(y);
par[x]=y;
}
struct edge{int c,a,b;};
bool comp(const edge& x,const edge& y){
return x.c<y.c;
}
int deg[400000];
bool od[400000];
typedef long long ll;
typedef pair<int,int> P;
ll ans=0,mod=1e9+7,p2[500001];
vector<P> G[400000];
vector<edge> es;
void dfs(int v,int pre){
bool ev=(deg[v]%2==0);
for(P p:G[v]){
int u=p.fs;
if(u==pre) continue;
dfs(u,v);
if(od[u]){
ev=!ev;
ans+=p2[p.sc];
ans%=mod;
}
}
od[v]=!ev;
}
int main(){
int N,M;
cin>>N>>M;
p2[0]=1;
rep(i,M) p2[i+1]=p2[i]*2%mod;
init(N);
rep(i,M){
int a,b;
cin>>a>>b;
es.pb({i+1,a-1,b-1});
deg[a-1]++;
deg[b-1]++;
}
sort(all(es),comp);
for(edge e:es){
if(same(e.a,e.b)) continue;
unite(e.a,e.b);
G[e.a].pb(P(e.b,e.c));
G[e.b].pb(P(e.a,e.c));
}
dfs(0,-1);
rep1(i,M) ans+=p2[i],ans%=mod;
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
C - ドライブ |
User |
sigma425 |
Language |
C++11 (GCC 4.8.1) |
Score |
110 |
Code Size |
1620 Byte |
Status |
AC |
Exec Time |
1033 ms |
Memory |
50572 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
40 / 40 |
70 / 70 |
Status |
|
|
|
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 |
40 ms |
10144 KB |
sample_02.txt |
AC |
40 ms |
10144 KB |
subtask1_01.txt |
AC |
38 ms |
10264 KB |
subtask1_02.txt |
AC |
40 ms |
10140 KB |
subtask1_03.txt |
AC |
38 ms |
10268 KB |
subtask1_04.txt |
AC |
41 ms |
10280 KB |
subtask1_05.txt |
AC |
45 ms |
10280 KB |
subtask1_06.txt |
AC |
43 ms |
10268 KB |
subtask1_07.txt |
AC |
43 ms |
10272 KB |
subtask1_08.txt |
AC |
43 ms |
10272 KB |
subtask1_09.txt |
AC |
46 ms |
10204 KB |
subtask1_10.txt |
AC |
41 ms |
10272 KB |
subtask1_11.txt |
AC |
41 ms |
10264 KB |
subtask1_12.txt |
AC |
42 ms |
10264 KB |
subtask1_13.txt |
AC |
44 ms |
10396 KB |
subtask1_14.txt |
AC |
42 ms |
10268 KB |
subtask1_15.txt |
AC |
45 ms |
10208 KB |
subtask1_16.txt |
AC |
41 ms |
10268 KB |
subtask1_17.txt |
AC |
46 ms |
10212 KB |
subtask1_18.txt |
AC |
42 ms |
10272 KB |
subtask2_01.txt |
AC |
1024 ms |
37900 KB |
subtask2_02.txt |
AC |
1033 ms |
38032 KB |
subtask2_03.txt |
AC |
898 ms |
38668 KB |
subtask2_04.txt |
AC |
1009 ms |
37260 KB |
subtask2_05.txt |
AC |
879 ms |
36108 KB |
subtask2_06.txt |
AC |
859 ms |
36368 KB |
subtask2_07.txt |
AC |
739 ms |
37128 KB |
subtask2_08.txt |
AC |
908 ms |
50572 KB |
subtask2_09.txt |
AC |
999 ms |
38284 KB |
subtask2_10.txt |
AC |
224 ms |
16540 KB |
subtask2_11.txt |
AC |
394 ms |
18836 KB |
subtask2_12.txt |
AC |
838 ms |
30348 KB |
subtask2_13.txt |
AC |
840 ms |
33160 KB |
subtask2_14.txt |
AC |
908 ms |
36492 KB |
subtask2_15.txt |
AC |
535 ms |
20376 KB |