Submission #353929
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)];} }; 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<Edge> Edges; 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); Edges es; UnionFind uf(N); REP(i, M){ int a, b; cin >> a >> b; a--; b--; even[a]++; even[b]++; ans = (ans + cost[i]) % MOD; if(!uf.findSet(a, b)){ uf.unionSet(a, b); es.push_back(Edge(a, b, i)); } } REP(i, N) even[i] %= 2; int evensum = 0; vi evennum(N, 0); vector<vi> g(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, g, even, evennum); RREP(i, es.size()){ int x = es[i].src, y = es[i].dst; int k = min(evennum[x], evennum[y]); if(k % 2 == 1 || (evensum - 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 | 2822 Byte |
Status | CE |
Compile Error
./Main.cpp:46:5: error: ‘Weight’ does not name a type ./Main.cpp:48:24: error: ‘Weight’ has not been declared ./Main.cpp: In constructor ‘Edge::Edge(int, int, int, int)’: ./Main.cpp:48:59: error: class ‘Edge’ does not have any field named ‘weight’ ./Main.cpp: In member function ‘bool Edge::operator<(const Edge&) const’: ./Main.cpp:49:51: error: ‘weight’ was not declared in this scope ./Main.cpp:49:63: error: ‘const struct Edge’ has no member named ‘weight’ ./Main.cpp: In function ‘int main()’: ./Main.cpp:93:9: error: ‘gs’ was not declared in this scope ./Main.cpp:102:37: error: ‘struct Edge’ has no member named ‘weight’