Submission #886928

#TimeUsernameProblemLanguageResultExecution timeMemory
886928vjudge1Usmjeri (COCI17_usmjeri)C++17
56 / 140
2106 ms262144 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; const int MOD = 1E9 + 7; const int MAXN = 3E5 + 5; const int LOG = 25; int p[LOG][MAXN]; int depth[MAXN], tin[MAXN], tout[MAXN]; int get(int a, int b) { for(int i = LOG -1; i >= 0; i--) { if(b & (1 << i)) { a = p[i][a]; } } return a; } int par[MAXN]; struct DSU { int n; DSU(int n) : n(n) { // 23 orz iota(par, par + n, 0); } int get(int x) { if(par[x] == x) { return x; } return par[x] = get(par[x]); } bool same(int a, int b) { return get(a) == get(b); } bool unite(int u, int v) { if(same(u, v)) { return false; } u = get(u); v = get(v); par[u] = v; return true; } }; int lca(int a, int b) { if(depth[a] > depth[b]) { swap(a, b); } b = get(b, depth[b] - depth[a]); if(a == b) { return a; } for(int lg = LOG -1; lg >= 0; lg--) { if(p[lg][a] != p[lg][b]) { a = p[lg][a]; b = p[lg][b]; } } return p[0][a]; } vector <pair <int, int>> adj[MAXN]; vector <pair <int, int>> bdj[MAXN]; map <pair <int, int>, int> edges; pair <int, int> mp(int a, int b) { return {min(a, b), max(a, b)}; } #define ONLINE_JUDGE void solve() { int n, m; cin >> n >> m; for(int i = 1; i <= n -1; i++) { int u, v; cin >> u >> v; adj[u].emplace_back(v, i); adj[v].emplace_back(u, i); edges[mp(u, v)] = i; } int timer = 0; function <void(int, int)> dfs = [&](int node, int par) -> void { tin[node] = timer++; p[0][node] = par; depth[node] = depth[par] +1; for(auto &[child, col] : adj[node]) { if(child != par) { dfs(child, node); } } tout[node] = timer++; }; dfs(1, 0); for(int lg = 1; lg < LOG; lg++) { for(int i = 1; i <= n; i++) { p[lg][i] = p[lg -1][p[lg -1][i]]; } } DSU dsu(n +1); function <void(int, int)> merge = [&](int node, int par) -> void { vector <int> vec; while(node != par) { assert(edges.count(mp(node, p[0][node]))); assert(edges.count(mp(node, p[0][node]))); vec.emplace_back(edges[mp(node, p[0][node])]); node = p[0][node]; } for(int i = 0; i +1 < int(vec.size()); i++) { bdj[vec[i]].emplace_back(vec[i +1], 0); bdj[vec[i +1]].emplace_back(vec[i], 0); } return; }; vector <array <int, 3>> queries(m +1); for(int i = 1; i <= m; i++) { int a, b; cin >> a >> b; int c = lca(a, b); queries[i] = {a, b, c}; if(a != c) { assert(tin[c] < tin[a] && tout[a] < tout[c]); merge(a, c); } if(b != c) { assert(tin[c] < tin[b] && tout[b] < tout[c]); merge(b, c); } if(a != c && b != c) { assert(tin[c] < min(tin[a], tin[b]) && max(tout[a], tout[b]) < tout[c]); assert(edges.count(mp(a, p[0][a]))); assert(edges.count(mp(b, p[0][b]))); bdj[edges[mp(a, p[0][a])]].emplace_back(edges[mp(b, p[0][b])], 1); bdj[edges[mp(b, p[0][b])]].emplace_back(edges[mp(a, p[0][a])], 1); } } vector <int> colors(n +1, -1); function <void(int, int, int)> paint = [&](int node, int par, int col) -> void { if(colors[node] != -1) { if(colors[node] != col) { cerr << node << " " << par << "\n"; cout << 0; exit(0); } return; } colors[node] = col; for(auto [child, c] : bdj[node]) { if(child != par) { dsu.unite(node, child); paint(child, node, col ^ c); } } return; }; for(int i = 1; i <= n -1; i++) { if(colors[i] == -1) { paint(i, 0, 0); } } for(int i = 1; i <= n -1; i++) { for(auto [child, c] : bdj[i]) { if(colors[i] != colors[child] ^ c) { cerr << i << " " << child << " -> " << colors[i] << " " << colors[child] << " :: " << c << "\n"; cout << 0; exit(0); } } } int ans = 1; for(int i = 1; i <= n -1; i++) { if(dsu.get(i) == i) { ans = (ans * 2) % MOD; } } cout << ans; return; } signed main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { solve(); } return 0; }

Compilation message (stderr)

usmjeri.cpp: In function 'void solve()':
usmjeri.cpp:198:26: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  198 |             if(colors[i] != colors[child] ^ c) {
#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...