Submission #237775

#TimeUsernameProblemLanguageResultExecution timeMemory
237775kartelUsmjeri (COCI17_usmjeri)C++14
140 / 140
533 ms83420 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-O3") #define F first #define S second #define pb push_back #define N +500500 #define MaxS N * N #define M ll(1e9 + 7) #define sz(x) (int)x.size() //#define re return #define oo ll(1e18) #define el '\n' #define pii pair <int, int> using namespace std; //using namespace __gnu_pbds; //typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef long long ll; typedef long double ld; int pred[N], pr[N], ra[N], tin[N], tout[N], de[N], up[N][23], col[N]; bool mk[N]; vector <pair <int, int> > paths; vector <int> g[N]; int n, m, i, bad = 0, j, x, y, v, u, tim; ll ans; int ispred(int x, int y) {return (tin[x] <= tin[y] && tout[x] >= tout[y]);} int lca(int x, int y) { for (int st = 20; st >= 0; st--) if (!ispred(up[x][st], y)) x = up[x][st]; return up[x][0]; } void dfs(int v, int pr, int d) { tin[v] = tim++; de[v] = d; up[v][0] = pr; pred[v] = pr; if (pr != 0) g[v].erase(find(g[v].begin(), g[v].end(), pr)); for (auto u : g[v]) dfs(u, v, d + 1); tout[v] = tim - 1; } int f(int x) { if (pr[x] != x) pr[x] = f(pr[x]); return pr[x]; } void link(int x, int y) {pr[f(x)] = f(y);} void check(int v, int c) { if (mk[v] && col[v] != c) bad = 1; if (mk[v]) return; mk[v] = 1; col[v] = c; for (auto u : g[v]) check(u, c ^ 1); } void fnd(int v) { if (v == 1) return; if (f(v) == f(pred[v])) { fnd(pred[v]); pred[v] = pred[pred[v]]; } } void path(int v, int u) { swap(v, u); fnd(v); while (de[u] < de[pred[v]]) { link(v, pred[v]); fnd(v = pred[v]); } } int main() { srand(time(0)); ios_base::sync_with_stdio(0); iostream::sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // in("input.txt"); // out("output.txt"); cin >> n >> m; for (i = 1; i <= n; i++) g[i].clear(), pr[i] = i, ra[i] = 1; for (i = 1; i < n; i++) { cin >> v >> u; g[v].pb(u); g[u].pb(v); } tim = 1; tin[0] = -1; tout[0] = N; dfs(1, 0, 0); for (int st = 1; st <= 20; st++) for (i = 1; i <= n; i++) up[i][st] = up[up[i][st - 1]][st - 1]; for (i = 1; i <= m; i++) { cin >> v >> u; if (u == v) continue; if (tin[v] > tin[u]) swap(v, u); if (tout[v] >= tout[u]) { path(v, u); } else { int lc = lca(u, v); path(lc, v); path(lc, u); paths.pb({u, v}); } } for (i = 1; i <= n; i++) g[i].clear(); for (auto x : paths) { int v = f(x.F); int u = f(x.S); if (v == u) {cout << "0";return 0;} // cout << u << " " << v << el; g[v].pb(u); g[u].pb(v); } bad = 0; for (i = 2; i <= n; i++) if (!mk[i]) check(i, 0); if (bad) {cout << "0";return 0;} for (auto x : paths) link(x.F, x.S); set <int> se; for (i = 2; i <= n; i++) se.insert(f(i)); ans = 1; for (i = 0; i < sz(se); i++) ans = (ans << 1ll) % M; cout << ans; } // x ^ 2 + y ^ 2 = 1 // x * a_i + y * b_i // a_i = -b_i * tan(alpha) // a_i / -b_i = tan(alpha) // alpha = atan(a_i / (-b_i))
#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...