Submission #353917
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;
const int INF = 1e9;
const int MOD = 1e9+7;
struct UnionFind {
vector<int> data;
UnionFind(int size) : data(size, -1) { }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
int size(int x) {
return -data[root(x)];
}
};
typedef int Weight;
struct Edge{
int src,dst;
Weight weight;
int rev;
Edge(int f, int t, Weight c, int rev=0):src(f),dst(t),weight(c),rev(rev){}
bool operator < (const Edge& re)const{ return weight > re.weight;}
};
typedef vector< vector<Edge> > Graph;
void add_edge(Graph &G, int s, int t, Weight cap){
G[s].push_back(Edge(s, t, cap, G[t].size()));
G[t].push_back(Edge(t, s, cap, G[s].size()-1));
}
typedef vector<Edge> Edges;
pair<Weight, Edges> minimumSpanningForest(const Graph &g) {
int n = g.size();
UnionFind uf(n);
priority_queue<Edge> Q;
REP(u, n) FOR(e, g[u]) if (u < e->dst) Q.push(*e);
Weight total = 0;
Edges F;
while (F.size() < n-1 && !Q.empty()) {
Edge e = Q.top(); Q.pop();
if (uf.unionSet(e.src, e.dst)) {
F.push_back(e);
total += e.weight;
}
}
return pair<Weight, Edges>(total, F);
}
int dfs(int pre, int v, vector<vi> &g, vi &even, vi &evennum){
int res = 0;
if(even[v]) res++;
if(pre != -1 && g[v].size() == 1) return res;
FOR(e, g[v]){
if((*e) == pre) continue;
res += dfs(v, *e, g, even, evennum);
}
evennum[v] = res;
return res;
}
int main(void){
int N, M;
cin >> N >> M;
vector<ll> cost(M, 2);
for(int i = 1; i < M; i++) (cost[i] = cost[i-1] * 2) %= MOD;
ll ans = 0LL;
vi even(N, 0);
Graph g(N);
REP(i, M){
int a, b;
cin >> a >> b;
a--; b--;
even[a]++; even[b]++;
ans = (ans + cost[i]) % MOD;
add_edge(g, a, b, i);
}
REP(i, N) even[i] %= 2;
pair<Weight, Edges> msf = minimumSpanningForest(g);
int evensum = 0;
Edges es = msf.second;
vi evennum(N, 0);
vector<vi> gs(N);
FOR(e, es){
int x = (*e).src, y = (*e).dst;
gs[x].push_back(y);
gs[y].push_back(x);
}
evensum = dfs(-1, 0, gs, even, evennum);
RREP(i, es.size()){
//cout << es[i].src << "*" << es[i].dst << ":" << es[i].weight << endl;
int x = es[i].src, y = es[i].dst;
int k = min(evennum[x], evennum[y]);
if(k % 2 == 1){
ans = (ans + cost[es[i].weight]) % MOD;
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ドライブ |
User |
no15_renne |
Language |
C++ (G++ 4.6.4) |
Score |
0 |
Code Size |
3600 Byte |
Status |
WA |
Exec Time |
1668 ms |
Memory |
90908 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
0 / 40 |
0 / 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 |
75 ms |
1136 KB |
sample_02.txt |
AC |
75 ms |
1128 KB |
subtask1_01.txt |
WA |
27 ms |
1076 KB |
subtask1_02.txt |
AC |
27 ms |
1168 KB |
subtask1_03.txt |
WA |
27 ms |
1104 KB |
subtask1_04.txt |
WA |
32 ms |
1460 KB |
subtask1_05.txt |
WA |
31 ms |
1460 KB |
subtask1_06.txt |
WA |
32 ms |
1436 KB |
subtask1_07.txt |
WA |
31 ms |
1456 KB |
subtask1_08.txt |
WA |
31 ms |
1460 KB |
subtask1_09.txt |
WA |
31 ms |
1492 KB |
subtask1_10.txt |
WA |
32 ms |
1460 KB |
subtask1_11.txt |
WA |
32 ms |
1456 KB |
subtask1_12.txt |
WA |
32 ms |
1460 KB |
subtask1_13.txt |
WA |
31 ms |
1712 KB |
subtask1_14.txt |
WA |
30 ms |
1332 KB |
subtask1_15.txt |
WA |
30 ms |
1200 KB |
subtask1_16.txt |
WA |
31 ms |
1456 KB |
subtask1_17.txt |
WA |
30 ms |
1324 KB |
subtask1_18.txt |
AC |
29 ms |
1328 KB |
subtask2_01.txt |
WA |
1550 ms |
76836 KB |
subtask2_02.txt |
WA |
1523 ms |
77000 KB |
subtask2_03.txt |
WA |
1315 ms |
75612 KB |
subtask2_04.txt |
WA |
1668 ms |
76992 KB |
subtask2_05.txt |
WA |
1555 ms |
71692 KB |
subtask2_06.txt |
WA |
1370 ms |
72008 KB |
subtask2_07.txt |
WA |
1151 ms |
71412 KB |
subtask2_08.txt |
WA |
1521 ms |
90908 KB |
subtask2_09.txt |
WA |
1639 ms |
76104 KB |
subtask2_10.txt |
WA |
318 ms |
18572 KB |
subtask2_11.txt |
WA |
480 ms |
27524 KB |
subtask2_12.txt |
WA |
1250 ms |
54664 KB |
subtask2_13.txt |
WA |
1340 ms |
66116 KB |
subtask2_14.txt |
WA |
1413 ms |
71964 KB |
subtask2_15.txt |
WA |
566 ms |
30640 KB |