Submission #59330

#TimeUsernameProblemLanguageResultExecution timeMemory
59330BenqUsmjeri (COCI17_usmjeri)C++14
140 / 140
1719 ms162560 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 100001; template<int SZ> struct DSU { int par[SZ], sz[SZ]; DSU() { F0R(i,SZ) par[i] = i, sz[i] = 1; } int get(int x) { // path compression if (par[x] != x) par[x] = get(par[x]); return par[x]; } bool unite(int x, int y) { // union-by-rank x = get(x), y = get(y); if (x == y) return 0; if (sz[x] < sz[y]) swap(x,y); sz[x] += sz[y], par[y] = x; return 1; } }; DSU<3<<20> D; // 1<<20, 1<<20, 1<<20 vector<vi> graph; bool existEdge[2][1<<20]; int get(int z, int x) { return x+((z+1)<<20); } void prop(int z, int ind) { if (ind >= (1<<19)) return; if (!existEdge[z][2*ind]) { existEdge[z][2*ind] = 1; D.unite(get(z,ind),get(z,2*ind)); prop(z,2*ind); } if (!existEdge[z][2*ind+1]) { existEdge[z][2*ind+1] = 1; D.unite(get(z,ind),get(z,2*ind+1)); prop(z,2*ind+1); } } void updSeg(int z, int x, int l, int r, int ind = 1, int lo = 0, int hi = (1<<19)-1) { if (r < lo || l > hi) return; if (l <= lo && hi <= r) { D.unite(x,get(z,ind)); prop(z,ind); return; } int mid = (lo+hi)/2; updSeg(z,x,l,r,2*ind,lo,mid); updSeg(z,x,l,r,2*ind+1,mid+1,hi); } template <int V> struct HeavyLight { // sum queries, sum updates int parent[V], heavy[V], depth[V]; int root[V], treePos[V]; void init() { int n = sz(graph)-1; FOR(i,1,n+1) heavy[i] = -1; parent[1] = -1, depth[1] = 0; dfs(1); for (int i = 1, currentPos = 0; i <= n; ++i) if (parent[i] == -1 || heavy[parent[i]] != i) for (int j = i; j != -1; j = heavy[j]) { root[j] = i; treePos[j] = currentPos++; } } int dfs(int v) { int size = 1, maxSubtree = 0; for (auto u : graph[v]) if (u != parent[v]) { parent[u] = v; depth[u] = depth[v] + 1; int subtree = dfs(u); if (subtree > maxSubtree) heavy[v] = u, maxSubtree = subtree; size += subtree; } return size; } void processPath(int x, int u, int v) { for (; root[u] != root[v]; ) { if (depth[root[u]] > depth[root[v]]) { updSeg(0, x, treePos[root[u]], treePos[u]); u = parent[root[u]]; } else { updSeg(1, x, treePos[root[v]], treePos[v]); v = parent[root[v]]; } } if (depth[u] > depth[v]) { updSeg(0, x, treePos[v]+1,treePos[u]); } else { updSeg(1, x, treePos[u]+1, treePos[v]); // assumes values are stored in edges, not vertices } } }; HeavyLight<1<<19> H; int N,M; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; graph.resize(N+1); F0R(i,N-1) { int a,b; cin >> a >> b; graph[a].pb(b), graph[b].pb(a); } H.init(); F0R(i,M) { int x,y; cin >> x >> y; H.processPath(2*i,x,y); H.processPath(2*i+1,y,x); } set<int> s; FOR(i,2,N+1) { int a = D.get(i-1+(3<<19)); int b = D.get(i-1+(5<<19)); if (a == b) { cout << 0; exit(0); } s.insert(a); s.insert(b); } ll res = 1; F0R(i,sz(s)/2) res = 2*res%MOD; cout << res; } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#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...