Submission #338133
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#define SIZE 400005
#define MOD 1000000007
using namespace std;
struct edge
{
int to,id;
edge(int to=0,int id=0):to(to),id(id){}
};
struct UF
{
int par[SIZE],rank[SIZE];
void init(int n)
{
for(int i=0;i<n;i++)
{
par[i]=i;
rank[i]=0;
}
}
int find(int x)
{
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y) return;
if(rank[x]<rank[y])
{
par[x]=y;
}
else
{
par[y]=x;
if(rank[x]==rank[y]) rank[x]++;
}
}
bool same(int x,int y)
{
return find(x)==find(y);
}
};
UF uf;
vector <edge> vec[SIZE];
int cnt[SIZE];
int dfs(int v,int p)
{
int ret=0;
for(int i=0;i<vec[v].size();i++)
{
edge e=vec[v][i];
if(e.to!=p)
{
ret+=dfs(e.to,v);
ret%=MOD;
cnt[v]^=cnt[e.to];
if(cnt[e.to]==0)
{
ret+=e.id;
ret%=MOD;
}
}
}
return ret;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
uf.init(n+2);
int rt=1,ret=0;
for(int i=0;i<m;i++)
{
rt<<=1;
rt%=MOD;
int a,b;
scanf("%d %d",&a,&b);a--;b--;
if(uf.same(a,b))
{
cnt[a]^=1;
cnt[b]^=1;
}
else
{
uf.unite(a,b);
vec[a].push_back(edge(b,rt));
vec[b].push_back(edge(a,rt));
}
ret+=rt;
ret%=MOD;
}
printf("%d\n",(ret+dfs(0,-1))%MOD);
return 0;
}
Submission Info
Submission Time
2015-02-14 20:14:57+0900
Task
C - ドライブ
User
yutaka1999
Language
C++ (G++ 4.6.4)
Score
110
Code Size
1529 Byte
Status
AC
Exec Time
698 ms
Memory
43944 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:83:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:91:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
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
45 ms
10152 KB
sample_02.txt
AC
43 ms
10152 KB
subtask1_01.txt
AC
39 ms
10140 KB
subtask1_02.txt
AC
41 ms
10264 KB
subtask1_03.txt
AC
42 ms
10092 KB
subtask1_04.txt
AC
40 ms
10272 KB
subtask1_05.txt
AC
43 ms
10216 KB
subtask1_06.txt
AC
42 ms
10276 KB
subtask1_07.txt
AC
39 ms
10272 KB
subtask1_08.txt
AC
40 ms
10148 KB
subtask1_09.txt
AC
41 ms
10280 KB
subtask1_10.txt
AC
43 ms
10244 KB
subtask1_11.txt
AC
41 ms
10280 KB
subtask1_12.txt
AC
42 ms
10280 KB
subtask1_13.txt
AC
43 ms
10404 KB
subtask1_14.txt
AC
43 ms
10148 KB
subtask1_15.txt
AC
39 ms
10144 KB
subtask1_16.txt
AC
41 ms
10280 KB
subtask1_17.txt
AC
41 ms
10272 KB
subtask1_18.txt
AC
40 ms
10152 KB
subtask2_01.txt
AC
682 ms
29352 KB
subtask2_02.txt
AC
678 ms
29536 KB
subtask2_03.txt
AC
490 ms
29964 KB
subtask2_04.txt
AC
674 ms
28576 KB
subtask2_05.txt
AC
635 ms
29600 KB
subtask2_06.txt
AC
639 ms
29728 KB
subtask2_07.txt
AC
381 ms
28812 KB
subtask2_08.txt
AC
698 ms
43944 KB
subtask2_09.txt
AC
653 ms
29732 KB
subtask2_10.txt
AC
154 ms
14556 KB
subtask2_11.txt
AC
137 ms
10792 KB
subtask2_12.txt
AC
421 ms
21276 KB
subtask2_13.txt
AC
607 ms
26148 KB
subtask2_14.txt
AC
603 ms
28836 KB
subtask2_15.txt
AC
163 ms
10148 KB