Submission #239609

#TimeUsernameProblemLanguageResultExecution timeMemory
239609NONAMEUsmjeri (COCI17_usmjeri)C++14
28 / 140
500 ms86096 KiB
#include <iostream> #include <vector> #include <set> using namespace std; const int N = 3e5 + 10; const int base = 1e9 + 7; int n, m, col[N], tin[N], tout[N], depth[N], pr[N], up[N][30], d[N], timer; bool mk[N]; vector <pair <int, int> > e; vector <int> g[N]; void paint(int v, int cl) { if (mk[v]) { if (col[v] != cl) { cout << 0; exit(0); } return; } mk[v] = 1; col[v] = cl; for (int to : g[v]) paint(to, cl ^ 1); } void dfs(int v, int pred = 0) { tin[v] = timer++; pr[v] = pred; up[v][0] = pred; for (int i = 1; i < 20; ++i) up[v][i] = up[up[v][i - 1]][i - 1]; for (int to : g[v]) { if (to == pred) continue; depth[to] = depth[v] + 1; dfs(to, v); } tout[v] = timer++; } bool upper(int x, int y) { return (tin[x] < tin[y]) && (tout[x] > tout[y]); } int _lca(int x, int y) { if (upper(x, y)) return x; if (upper(y, x)) return y; for (int i = 19; i >= 0; --i) if (!upper(up[x][i], y)) x = up[x][i]; return up[x][0]; } int f(int x) { return (x == d[x]) ? x : d[x] = f(d[x]); } void find(int v) { if (!v) return; if (f(pr[v]) == f(v)) { find(pr[v]); pr[v] = pr[pr[v]]; } } void path(int v, int u) { find(v); while (depth[pr[v]] > depth[u]) { d[f(v)] = f(pr[v]); find(v = pr[v]); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < n - 1; ++i) { int x, y; cin >> x >> y; x--; y--; g[x].push_back(y); g[y].push_back(x); } dfs(0); for (int i = 0; i < n; ++i) d[i] = i; for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; x--; y--; if (x == y) continue; if (tin[x] > tin[y]) swap(x, y); if (tout[x] > tout[y]) path(y, x); else { int lca = _lca(x, y); path(x, lca); path(y, lca); e.push_back(make_pair(x, y)); } } //for (int i = 0; i < n; ++i) //cout << f(i) << ' '; //cout << '\n'; for (int i = 0; i < n; ++i) g[i].clear(); for (auto a : e) { int x = f(a.first); int y = f(a.second); if (x == y) { cout << 0; return 0; } g[x].push_back(y); g[y].push_back(x); } for (int i = 0; i < n; ++i) if (!mk[i]) paint(i, 0); for (auto a : e) pr[f(a.first)] = f(a.second); set <int> s; s.clear(); for (int i = 1; i < n; ++i) s.insert(f(i)); int ans = 1; for (int i = 0; i < int(s.size()); ++i) ans = (ans + ans) % base; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...