Submission #235762

#TimeUsernameProblemLanguageResultExecution timeMemory
235762VEGAnnUsmjeri (COCI17_usmjeri)C++14
140 / 140
667 ms74292 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define MP make_pair #define ft first #define sd second #define PB push_back #define pli pair<ll,int> using namespace std; typedef long long ll; const int N = 300100; const int PW = 20; const int oo = 2e9; const int md = int(1e9) + 7; vector<int> g[N], gr[N]; int n, m, pr[N], ans = 1, up[N][PW], tin[N], tout[N], tt = 0, ad[N]; int V[N], U[N], col[N]; int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); } void dfs(int v, int p){ up[v][0] = p; for (int po = 1; po < PW; po++) up[v][po] = up[up[v][po - 1]][po - 1]; tin[v] = ++tt; for (int u : g[v]){ if (p == u) continue; dfs(u, v); } tout[v] = tt; } bool upper(int a, int b){ return (tin[a] <= tin[b] && tout[a] >= tout[b]); } int lca(int a, int b){ if (upper(a, b)) return a; if (upper(b, a)) return b; for (int po = PW - 1; po >= 0; po--) if (!upper(up[a][po], b)) a = up[a][po]; return up[a][0]; } int pra(int a, int b){ for (int po = PW - 1; po >= 0; po--) if (!upper(up[a][po], b)) a = up[a][po]; return a; } void DFS(int v){ for (int u : g[v]){ if (u == up[v][0]) continue; DFS(u); ad[v] += ad[u]; } if (ad[v] > 0) pr[get(v)] = get(up[v][0]); } void BAD(){ cout << 0; exit(0); } void rec(int v, int ncl){ if (col[v] > 0){ if (col[v] != ncl) BAD(); return; } col[v] = ncl; for (int u : gr[v]) rec(u, 3 - ncl); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef _LOCAL freopen("in.txt","r",stdin); #endif // _LOCAL cin >> n >> m; for (int i = 1; i < n; i++){ int x, y; cin >> x >> y; x--; y--; g[x].PB(y); g[y].PB(x); pr[i] = i; } dfs(0, 0); for (int i = 0; i < m; i++){ int x, y; cin >> x >> y; x--; y--; int lc = lca(x, y); if (x != lc) swap(x, y); U[i] = x; V[i] = y; if (x == lc){ ad[y]++; int PR = pra(y, x); ad[PR]--; } else { ad[x]++; ad[y]++; int pr1 = pra(x, y); int pr2 = pra(y, x); ad[pr1]--; ad[pr2]--; } } DFS(0); for (int i = 0; i < m; i++){ int x = get(U[i]), y = get(V[i]); if (lca(U[i], V[i]) == U[i]) continue; if (x == y) BAD(); gr[x].PB(y); gr[y].PB(x); } for (int i = 1; i < n; i++){ int x = get(i); if (col[x] > 0) continue; ans += ans; if (ans >= md) ans -= md; rec(x, 1); } cout << ans; 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...