Submission #1229884

#TimeUsernameProblemLanguageResultExecution timeMemory
1229884DedibeatUsmjeri (COCI17_usmjeri)C++20
28 / 140
270 ms78904 KiB
#include <bits/stdc++.h> using namespace std; int n, l; vector<vector<int>> adj; int timer; vector<int> tin, tout, vis; vector<vector<int>> up; void dfs(int v, int p) { tin[v] = ++timer; up[v][0] = p; for (int i = 1; i <= l; ++i) { up[v][i] = up[ up[v][i-1] ][i-1]; } for (int u : adj[v]) { if (u != p) { dfs(u, v); } } tout[v] = ++timer; } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int LCA(int u, int v) { if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = l; i >= 0; --i) { if (!is_ancestor(up[u][i], v)) { u = up[u][i]; } } return up[u][0]; } void preprocess(int root) { tin.assign(n + 1, 0); tout.assign(n + 1, 0); timer = 0; l = ceil(log2(n + 1)); up.assign(n + 1, vector<int>(l + 1, 0)); dfs(root, root); } static const int MAXN = 300005; vector<pair<int,int>> g[MAXN]; int color[MAXN]; int dfs2(int v) { int ok = 1; //cout << "vis" << v << endl; for (auto [u, rel] : g[v]) { if (color[u] == 0) { color[u] = color[v] ^ rel; ok &= dfs2(u); } else if (color[u] != (color[v] ^ rel)) { return 0; } } return ok; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m; cin >> n >> m; adj.assign(n + 1, {}); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } preprocess(1); vis.assign(n + 1, 0); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; int lca = LCA(a, b); //cout << lca << endl; for (int v = a; v != lca; v = up[v][0]) { if (vis[v] || up[v][0] == lca) break; //cout << "at :" << v << " par :" << up[v][0] << endl; vis[v] = 1; g[v].emplace_back(up[v][0], 0); g[up[v][0]].emplace_back(v, 0); } for (int v = b; v != lca; v = up[v][0]) { if (vis[v] || up[v][0] == lca) break; //cout << "at :" << v << " par :" << up[v][0] << endl; vis[v] = 1; g[v].emplace_back(up[v][0], 0); g[up[v][0]].emplace_back(v, 0); } if(lca == a || lca == b) continue; g[a].emplace_back(b, 3); g[b].emplace_back(a, 3); } int cnt = 0; for (int i = 2; i <= n; i++) { if (color[i] == 0) { color[i] = 1; cnt++; //cout << i << endl; if (!dfs2(i)) { cout << "0\n"; return 0; } } } const int MOD = 1e9 + 7; long long ans = 1; for (int i = 0; i < cnt; i++) { ans = (ans * 2) % MOD; } cout << ans << "\n"; return 0; }
#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...