Submission #591266

#TimeUsernameProblemLanguageResultExecution timeMemory
591266Loki_NguyenUsmjeri (COCI17_usmjeri)C++14
140 / 140
381 ms77588 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll, int> #define pii pair<int, int> #define fi first #define se second #define pb push_back const int N = 3e5 + 3; const int M = 1 << 24; const int mod = 1e9 + 7; const int base = 300; const ll inf = 1e12; int pw(int k, int n) { int total = 1; for (; n; n >>= 1) { if (n & 1) total = total * k % mod; k = k * k % mod; } return total; } int m, n, t, k, a[N], ans, b[N * 2], c[N], d[N], lab[N * 2], tong, h[N], P[N][20]; vector<int> adj[N]; void dfs(int u, int p = 0) { for (int v : adj[u]) { if (v == p) continue; h[v] = h[u] + 1; P[v][0] = u; for (int i = 1; i <= 18; i++) P[v][i] = P[P[v][i - 1]][i - 1]; dfs(v, u); } } int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); int log = log2(h[u]); for (int i = log; i >= 0; i--) { if (h[u] >= h[v] + (1 << i)) u = P[u][i]; } if (u == v) return u; for (int i = log; i >= 0; i--) { if (P[u][i] && P[u][i] != P[v][i]) { u = P[u][i]; v = P[v][i]; } } return P[v][0]; } int fpar(int u, int dis) { for (int i = 18; i >= 0; i--) if (dis >> i & 1) u = P[u][i]; return u; } int findp(int u) { return lab[u] < 0 ? u : lab[u] = findp(lab[u]); } void hop(int u, int v) { u = findp(u); v = findp(v); if (u == v) return; if (lab[u] > lab[v]) swap(u, v); lab[u] += lab[v]; lab[v] = u; } void cal(int u, int p = 0) { for (int v : adj[u]) { if (v == p) continue; cal(v, u); d[u] += d[v]; } if (d[u] && p) { hop(u, p); hop(u + n, p + n); } } void sol() { cin >> n >> m; fill_n(lab, n * 2 + 1, -1); for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; adj[x].pb(y); adj[y].pb(x); } dfs(1); for (int i = 1; i <= m; i++) { int x, y, z, lx = 0, ly = 0; cin >> x >> y; z = lca(x, y); if (z != x) { lx = fpar(x, h[x] - h[z] - 1); ++d[x]; --d[lx]; } if (z != y) { ly = fpar(y, h[y] - h[z] - 1); ++d[y]; --d[ly]; } if (lx && ly) { hop(lx, ly + n); hop(ly, lx + n); } //cout << z << " " << lx << " " << ly << '\n'; } cal(1); ans = 1; for (int i = 2; i <= n; i++) { if (findp(i) == findp(i + n)) { cout << 0; return; } if (!b[findp(i)]) { b[findp(i)] = 1; ans = ans * 2 % mod; } if (!b[findp(i + n)]) { b[findp(i + n)] = 1; // ans = ans * 2 % mod; } } cout << ans; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "tests" if (fopen(task ".inp", "r")) { freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } int ntest = 1; // cin >> ntest; while (ntest-- > 0) sol(); } /* 10 10 259008492 685257993 684081919 849336162 185724174 230558609 147159919 225162936 734023603 130213023 2 1 4 2 4 7 2 2 8 2 4 10 2 5 8 2 5 6 2 1 10 2 3 8 2 1 8 2 2 4 2 1 6 */

Compilation message (stderr)

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
usmjeri.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...