Submission #642498

#TimeUsernameProblemLanguageResultExecution timeMemory
642498FedShatUsmjeri (COCI17_usmjeri)C++17
56 / 140
780 ms262144 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int INF = numeric_limits<int>::max() / 2; constexpr ll INFLL = numeric_limits<ll>::max() / 2; template<class T> istream &operator>>(istream &is, vector<T> &a) { for (auto &i : a) { is >> i; } return is; } constexpr int mod = 1e9 + 7; struct BinaryJumps { static constexpr int k = 20; vector<vector<int>> up; vector<int> depth; BinaryJumps() { } BinaryJumps(int n) { up.resize(k, vector<int>(n)); depth.resize(n); } void add_leaf(int v, int p) { up[0][v] = p; depth[v] = depth[p] + 1; for (int i = 1; i < k; ++i) { up[i][v] = up[i - 1][up[i - 1][v]]; } } int up_k(int v, int d) { for (int i = k - 1; i >= 0; --i) { if (d >= (1 << i)) { v = up[i][v]; d -= (1 << i); } } return v; } int LCA(int u, int v) { if (depth[u] < depth[v]) { swap(u, v); } u = up_k(u, depth[u] - depth[v]); for (int i = k - 1; i >= 0; --i) { if (up[i][u] != up[i][v]) { u = up[i][u]; v = up[i][v]; } } if (u == v) { return u; } return up[0][u]; } }; vector<vector<int>> g; vector<int> par, sz; BinaryJumps t; void dfs(int v, int p) { par[v] = p; sz[v] = 1; for (auto u : g[v]) { if (u != p) { t.add_leaf(u, v); dfs(u, v); sz[v] += sz[u]; } } if (p != -1) { g[v].erase(find(g[v].begin(), g[v].end(), p)); } sort(g[v].begin(), g[v].end(), [&](int a, int b) { return sz[a] > sz[b]; }); } vector<int> tour, tin, tout, head; void dfs_hld(int v) { tin[v] = tour.size(); tour.push_back(v); for (auto u : g[v]) { if (u == g[v][0]) { head[u] = head[v]; } else { head[u] = u; } dfs_hld(u); } tout[v] = tour.size(); } bool is_anc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; } vector<vector<pair<int, int>>> gr; int n; void add_edge(int u, int v, int c) { gr[u].push_back({v, c}); gr[v].push_back({u, c}); } void build(int v, int l, int r) { if (l + 1 == r) { add_edge(v + n, l, 1); return; } add_edge(v + n, 2 * v + 1 + n, 1); add_edge(v + n, 2 * v + 2, 1); int m = (l + r) / 2; build(2 * v + 1, l, m); build(2 * v + 2, m, r); } void add_edges(int v, int l, int r, int li, int ri, int i) { if (li >= r || l >= ri) { return; } if (li <= l && r <= ri) { add_edge(i, v + n, 1); return; } int m = (l + r) / 2; add_edges(2 * v + 1, l, m, li, ri, i); add_edges(2 * v + 2, m, r, li, ri, i); } void add_edges_stupid(int l, int r, int v) {// [l; r) for (int i = l; i < r; ++i) { int u = tour[i]; add_edge(u, v, 1); } } vector<int> color; bool ok = 1; void dfs2(int v) { for (auto [u, c] : gr[v]) { int cur = (c ? color[v] : color[v] ^ 1); if (color[u] == -1) { color[u] = cur; dfs2(u); } else { if (color[u] != cur) { ok = 0; } } } } int main() { cin.tie(0)->sync_with_stdio(0); #ifdef __APPLE__ freopen("input.txt", "r", stdin); #endif int n, q; cin >> n >> q; g.resize(n); for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; --u; --v; g[u].push_back(v); g[v].push_back(u); } t = BinaryJumps(n); par.resize(n); sz.resize(n); dfs(0, -1); gr.resize(n); head.resize(n); tin.resize(n); tout.resize(n); dfs_hld(0); while (q--) { int u, v; cin >> u >> v; --u; --v; if (t.depth[u] < t.depth[v]) { swap(u, v); } int l = t.LCA(u, v); if (l == v) {// verticals // int curu = u; // while (par[curu] != l) { // add_edge(curu, par[curu], 1);// equal // curu = par[curu]; // } int uu = t.up_k(u, t.depth[u] - t.depth[v] - 1); { int cur = u; while (!is_anc(head[cur], uu)) { add_edges_stupid(tin[head[cur]], tin[cur] + 1, u); cur = par[head[cur]]; } add_edges_stupid(tin[uu], tin[cur] + 1, u); } } else { // int curu = u; // while (par[curu] != l) { // add_edge(curu, par[curu], 1);// equal // curu = par[curu]; // } // int curv = v; // while (par[curv] != l) { // add_edge(curv, par[curv], 1);// equal // curv = par[curv]; // } // add_edge(curu, curv, 0); int uu = t.up_k(u, t.depth[u] - t.depth[l] - 1); { int cur = u; while (!is_anc(head[cur], uu)) { add_edges_stupid(tin[head[cur]], tin[cur] + 1, u); cur = par[head[cur]]; } add_edges_stupid(tin[uu], tin[cur] + 1, u); } int vv = t.up_k(v, t.depth[v] - t.depth[l] - 1); { int cur = v; while (!is_anc(head[cur], vv)) { add_edges_stupid(tin[head[cur]], tin[cur] + 1, v); cur = par[head[cur]]; } add_edges_stupid(tin[vv], tin[cur] + 1, v); } add_edge(uu, vv, 0); } } int ans = 1; color.resize(n, -1); for (int i = 1; i < n; ++i) { if (color[i] == -1) { color[i] = 0; dfs2(i); ans = (ans * 2ll) % mod; } } if (!ok) { cout << "0\n"; } else { 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...