Submission #570443

#TimeUsernameProblemLanguageResultExecution timeMemory
570443aryan12Usmjeri (COCI17_usmjeri)C++17
140 / 140
788 ms105456 KiB
#include <bits/stdc++.h> using namespace std; #define int long long mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 3e5 + 5, M = 3e5 + 5, MOD = 1e9 + 7; int depth[N], min_depth[N]; vector<int> g[N]; vector<array<int, 2> > g2[N]; int dp[19][N]; int color[N]; bool vis[N]; void dfs(int node, int par) { dp[0][node] = par; for(int to: g[node]) { if(to == par) continue; depth[to] = depth[node] + 1; min_depth[to] = depth[to]; dfs(to, node); } } int LCA(int x, int y) { if(depth[x] > depth[y]) swap(x, y); int diff = depth[y] - depth[x]; for(int i = 18; i >= 0; i--) { if(diff & (1 << i)) { y = dp[i][y]; } } if(x == y) return x; for(int i = 18; i >= 0; i--) { if(dp[i][x] != dp[i][y]) { x = dp[i][x]; y = dp[i][y]; } } return dp[0][x]; } void again_dfs(int node, int par) { for(int to: g[node]) { if(to == par) continue; // cout << "to = " << to << ", node = " << node << "\n"; again_dfs(to, node); min_depth[node] = min(min_depth[node], min_depth[to]); if(min_depth[to] < depth[node]) { // cout << to << " <-> " << node << " with 0\n"; g2[to].push_back({node, 0}); g2[node].push_back({to, 0}); } } } bool dfs_check(int node, int cur_color) { vis[node] = true; if(color[node] == 0 || color[node] == cur_color) { color[node] = cur_color; } if(color[node] != cur_color) return false; for(auto [to, wt]: g2[node]) { int next_color = (wt == 0) ? cur_color : 3 - cur_color; if(color[to] != 0 && color[to] != next_color) return false; if(vis[to]) continue; if(!dfs_check(to, next_color)) return false; } return true; } void Solve() { int n, m; cin >> n >> m; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } depth[1] = 0; min_depth[1] = 0; dfs(1, -1); for(int i = 1; i < 19; i++) { for(int j = 1; j <= n; j++) { if(dp[i - 1][j] == -1) { dp[i][j] = -1; } else { dp[i][j] = dp[i - 1][dp[i - 1][j]]; } } } for(int i = 1; i <= m; i++) { int u, v; cin >> u >> v; int lca = LCA(u, v); min_depth[u] = min(min_depth[u], depth[lca]); min_depth[v] = min(min_depth[v], depth[lca]); if(lca != u && lca != v) { g2[u].push_back({v, 1}); g2[v].push_back({u, 1}); // cout << u << " <-> " << v << " with 1\n"; } } again_dfs(1, -1); int ans = 1; for(int i = 2; i <= n; i++) { if(!vis[i]) { ans = (ans * 2) % MOD; } if(!vis[i] && !dfs_check(i, 1)) { cout << "0\n"; return; } } cout << ans << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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...