Submission #337991
Source Code Expand
#include <stdio.h> #include <algorithm> #include <iostream> #include <vector> using namespace std; #define pb push_back #define mp make_pair #define mod 1000000007 #define fi first #define sc second typedef long long ll; typedef pair<int,int> P; int n,m; vector<P>ed; int t[500005]; int par[400005]; int ran[400005]; void init() { for(int i=0;i<400005;i++) par[i]=i,ran[i]=0; } int find(int x) { if(par[x] == x) return x; else return par[x]=find(par[x]); } void unite(int x,int y) { x=find(x); y=find(y); if(x == y) return ; if(ran[x]<ran[y]) par[x]=par[y]; else { par[y]=par[x]; if(ran[x] == ran[y]) ran[x]++; } } bool same(int x,int y) { return find(x)==find(y); } vector<P>edge[400005]; int p[400005]; bool d[500005]; int dfs(int v,int u) { int ret = p[v]; for(int i=0;i<edge[v].size();i++) { int x = edge[v][i].fi; if(x == u) continue; int a = dfs(x,v); ret += a; if(a%2 == 1) d[edge[v][i].sc] = true; } return ret; } int main() { scanf("%d%d",&n,&m); t[0] = 1; for(int i=1;i<=500001;i++) t[i] = (t[i-1]*2)%mod; for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); ed.pb(mp(a,b)); p[a] ^= 1; p[b] ^= 1; } init(); for(int i=0;i<m;i++) { if(!same(ed[i].fi,ed[i].sc)) { unite(ed[i].fi,ed[i].sc); edge[ed[i].fi].pb(mp(ed[i].sc,i)); edge[ed[i].sc].pb(mp(ed[i].fi,i)); } } dfs(1,-1); int res = 0; for(int i=0;i<m;i++) { if(d[i]) res = (res+t[i+2])%mod; else res = (res+t[i+1])%mod; } cout << res << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - ドライブ |
User | IH19980412 |
Language | C++ (G++ 4.6.4) |
Score | 110 |
Code Size | 1579 Byte |
Status | AC |
Exec Time | 754 ms |
Memory | 46104 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:66:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] ./Main.cpp:72:31: 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 | 51 ms | 15264 KB |
sample_02.txt | AC | 51 ms | 15208 KB |
subtask1_01.txt | AC | 49 ms | 15240 KB |
subtask1_02.txt | AC | 48 ms | 15272 KB |
subtask1_03.txt | AC | 50 ms | 15140 KB |
subtask1_04.txt | AC | 50 ms | 15276 KB |
subtask1_05.txt | AC | 50 ms | 15272 KB |
subtask1_06.txt | AC | 49 ms | 15260 KB |
subtask1_07.txt | AC | 50 ms | 15344 KB |
subtask1_08.txt | AC | 49 ms | 15268 KB |
subtask1_09.txt | AC | 50 ms | 15264 KB |
subtask1_10.txt | AC | 51 ms | 15340 KB |
subtask1_11.txt | AC | 49 ms | 15272 KB |
subtask1_12.txt | AC | 49 ms | 15400 KB |
subtask1_13.txt | AC | 52 ms | 15472 KB |
subtask1_14.txt | AC | 49 ms | 15300 KB |
subtask1_15.txt | AC | 51 ms | 15268 KB |
subtask1_16.txt | AC | 51 ms | 15388 KB |
subtask1_17.txt | AC | 47 ms | 15272 KB |
subtask1_18.txt | AC | 48 ms | 15272 KB |
subtask2_01.txt | AC | 698 ms | 35728 KB |
subtask2_02.txt | AC | 688 ms | 35804 KB |
subtask2_03.txt | AC | 515 ms | 36364 KB |
subtask2_04.txt | AC | 726 ms | 34972 KB |
subtask2_05.txt | AC | 614 ms | 34968 KB |
subtask2_06.txt | AC | 614 ms | 35216 KB |
subtask2_07.txt | AC | 412 ms | 35860 KB |
subtask2_08.txt | AC | 754 ms | 46104 KB |
subtask2_09.txt | AC | 654 ms | 35988 KB |
subtask2_10.txt | AC | 153 ms | 19868 KB |
subtask2_11.txt | AC | 157 ms | 18200 KB |
subtask2_12.txt | AC | 439 ms | 28948 KB |
subtask2_13.txt | AC | 589 ms | 32140 KB |
subtask2_14.txt | AC | 642 ms | 34828 KB |
subtask2_15.txt | AC | 195 ms | 19212 KB |