Submission #338134
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
711 ms
Memory
44048 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
42 ms
10144 KB
sample_02.txt
AC
42 ms
10144 KB
subtask1_01.txt
AC
39 ms
10144 KB
subtask1_02.txt
AC
40 ms
10152 KB
subtask1_03.txt
AC
39 ms
10100 KB
subtask1_04.txt
AC
42 ms
10276 KB
subtask1_05.txt
AC
40 ms
10272 KB
subtask1_06.txt
AC
41 ms
10280 KB
subtask1_07.txt
AC
39 ms
10276 KB
subtask1_08.txt
AC
40 ms
10156 KB
subtask1_09.txt
AC
42 ms
10268 KB
subtask1_10.txt
AC
41 ms
10284 KB
subtask1_11.txt
AC
42 ms
10276 KB
subtask1_12.txt
AC
39 ms
10252 KB
subtask1_13.txt
AC
42 ms
10352 KB
subtask1_14.txt
AC
41 ms
10152 KB
subtask1_15.txt
AC
41 ms
10148 KB
subtask1_16.txt
AC
41 ms
10276 KB
subtask1_17.txt
AC
40 ms
10144 KB
subtask1_18.txt
AC
39 ms
10152 KB
subtask2_01.txt
AC
693 ms
29300 KB
subtask2_02.txt
AC
707 ms
29472 KB
subtask2_03.txt
AC
512 ms
29964 KB
subtask2_04.txt
AC
696 ms
28656 KB
subtask2_05.txt
AC
660 ms
29476 KB
subtask2_06.txt
AC
616 ms
29792 KB
subtask2_07.txt
AC
381 ms
28828 KB
subtask2_08.txt
AC
711 ms
44048 KB
subtask2_09.txt
AC
677 ms
29736 KB
subtask2_10.txt
AC
164 ms
14496 KB
subtask2_11.txt
AC
134 ms
10860 KB
subtask2_12.txt
AC
429 ms
21276 KB
subtask2_13.txt
AC
638 ms
26148 KB
subtask2_14.txt
AC
624 ms
28824 KB
subtask2_15.txt
AC
162 ms
10152 KB