Submission #1693310
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount
#define INF 1e18
#define mod 1000000007
struct UnionFind{
vector<int> v;
UnionFind(int n) : v(n, -1) {}
void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }
int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (-v[x] < -v[y]) swap(x, y);
v[x] += v[y]; v[y] = x;
return true;
}
bool root(int x) { return v[x] < 0; }
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return -v[find(x)]; }
};
ll mod_pow(ll a,ll n){
ll res=1;
while(n>0){
if(n&1)res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
ll n,m;
P es[500050];
ll deg[400040];
vector<P> g[400040];
ll cost[500050];
P dfs(ll v,ll pre){
ll res=0;
ll cnt=deg[v];
for(P e : g[v]){
if(e.fi==pre)continue;
P tmp=dfs(e.fi,v);
cnt+=tmp.se;
res+=tmp.fi;
if(tmp.se)res=(res+e.se)%mod;
}
cnt%=2;
return P(res,cnt);
}
int main(){
rep(i,500050){
cost[i]=mod_pow(2,i+1);
}
cin>>n>>m;
rep(i,m){
cin>>es[i].fi>>es[i].se;
es[i].fi--; es[i].se--;
deg[es[i].fi]++;
deg[es[i].se]++;
}
UnionFind uf(n);
rep(i,m){
if(uf.same(es[i].fi,es[i].se))continue;
uf.unite(es[i].fi,es[i].se);
g[es[i].fi].push_back(P(es[i].se,cost[i]));
g[es[i].se].push_back(P(es[i].fi,cost[i]));
}
rep(i,n)deg[i]%=2;
ll res=0;
rep(i,m)res=(res+cost[i])%mod;
cout<<(res+dfs(0,-1).fi)%mod<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ドライブ |
User |
yamad |
Language |
C++14 (GCC 5.4.1) |
Score |
110 |
Code Size |
2193 Byte |
Status |
AC |
Exec Time |
671 ms |
Memory |
61952 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 |
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_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 |
54 ms |
16640 KB |
sample_02.txt |
AC |
54 ms |
16640 KB |
subtask1_01.txt |
AC |
54 ms |
16640 KB |
subtask1_02.txt |
AC |
54 ms |
16640 KB |
subtask1_03.txt |
AC |
54 ms |
16640 KB |
subtask1_04.txt |
AC |
56 ms |
16768 KB |
subtask1_05.txt |
AC |
56 ms |
16768 KB |
subtask1_06.txt |
AC |
56 ms |
16768 KB |
subtask1_07.txt |
AC |
56 ms |
16768 KB |
subtask1_08.txt |
AC |
56 ms |
16768 KB |
subtask1_09.txt |
AC |
56 ms |
16768 KB |
subtask1_10.txt |
AC |
56 ms |
16768 KB |
subtask1_11.txt |
AC |
56 ms |
16768 KB |
subtask1_12.txt |
AC |
56 ms |
16768 KB |
subtask1_13.txt |
AC |
56 ms |
16896 KB |
subtask1_14.txt |
AC |
56 ms |
16768 KB |
subtask1_15.txt |
AC |
55 ms |
16640 KB |
subtask1_16.txt |
AC |
56 ms |
16768 KB |
subtask1_17.txt |
AC |
56 ms |
16640 KB |
subtask1_18.txt |
AC |
55 ms |
16640 KB |
subtask2_01.txt |
AC |
641 ms |
46592 KB |
subtask2_02.txt |
AC |
646 ms |
46464 KB |
subtask2_03.txt |
AC |
540 ms |
46700 KB |
subtask2_04.txt |
AC |
671 ms |
47488 KB |
subtask2_05.txt |
AC |
589 ms |
45440 KB |
subtask2_06.txt |
AC |
573 ms |
45056 KB |
subtask2_07.txt |
AC |
436 ms |
44776 KB |
subtask2_08.txt |
AC |
647 ms |
61952 KB |
subtask2_09.txt |
AC |
649 ms |
47360 KB |
subtask2_10.txt |
AC |
147 ms |
21760 KB |
subtask2_11.txt |
AC |
207 ms |
21504 KB |
subtask2_12.txt |
AC |
433 ms |
36464 KB |
subtask2_13.txt |
AC |
550 ms |
43264 KB |
subtask2_14.txt |
AC |
583 ms |
45568 KB |
subtask2_15.txt |
AC |
266 ms |
22528 KB |