Submission #666732

#TimeUsernameProblemLanguageResultExecution timeMemory
666732NursikTraffickers (RMI18_traffickers)C++14
100 / 100
2160 ms64640 KiB
#include <stdio.h> #include <algorithm> #include <bitset> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> //#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define f first #define s second #define ld long double const ll maxn = 1e5 + 1, maxm = 1e6 + 1; const ll mod = 1e9 + 7, inf = 1e9, block = 550, hb = 31, base = 1000050017, biginf = 5e18; const ld eps = 1e-9; int n, k, q, timer, lac; int tin[maxn], tout[maxn], used[maxn], par[maxn], p[maxn], sz[maxn], anc[maxn], zu[maxn], zu2[maxn]; vector<int> g[maxn]; vector<pair<int, int>> zp[maxn]; int type[maxn], uu[maxn], vv[maxn], t[maxn], t2[maxn], lc[maxn];; int get(int v){ if (v == p[v]) return v; return p[v] = get(p[v]); } void unite(int a, int b, int x){ a = get(a), b = get(b); if (sz[a] > sz[b]) swap(a, b); p[a] = b, anc[b] = x; sz[b] += sz[a]; } void dfs(int v = 1, int pr = 0){ par[v] = pr, tin[v] = ++timer; used[v] = 1; anc[v] = v; for (auto to : g[v]){ if (to != pr){ dfs(to, v); unite(to, v, v); } } for (auto it : zp[v]){ int ver = it.f, x = it.s; if (used[ver]){ lc[x] = anc[get(ver)]; } } tout[v] = ++timer; } struct fenwick{ int f[maxn]; void upd(int pos, int val){ for (int i = pos; i <= timer; i |= (i + 1)){ f[i] += val; } } int get(int pos){ int res = 0; for (int i = pos; i >= 1; i = (i & (i + 1)) - 1){ res += f[i]; } return res; } } rt[21][20]; ll calc(int x, int d, int pac, int y){ ll ky = y / d, k2 = y % d; ll z = rt[d][pac].get(x); ll sum = ky * z + (k2 >= pac) * z; return sum; } ll calc2(int u, int v, int x){ if (x < 0) return 0; ll res = 0; ll parik = par[lac]; for (int i = 1; i <= 20; ++i){ for (int j = 0; j < i; ++j){ ll add = calc(tin[u], i, j, x) + calc(tin[v], i, j, x) - calc(tin[lac], i, j, x); if (parik > 0){ add -= calc(tin[parik], i, j, x); } res += add; } } return res; } void upd(int u, int v, int x, int is){ vector<int> path; while (u != x){ path.pb(u); u = par[u]; } vector<int> pp; while (v != x){ pp.pb(v); v = par[v]; } pp.pb(x); reverse(pp.begin(), pp.end()); for (auto it : pp){ path.pb(it); } int len = (int)path.size(); if (is == 1){ for (int i = 0; i < len; ++i){ rt[len][i].upd(tin[path[i]], 1); rt[len][i].upd(tout[path[i]], -1); } } else{ for (int i = 0; i < len; ++i){ rt[len][i].upd(tin[path[i]], -1); rt[len][i].upd(tout[path[i]], 1); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; ++i){ sz[i] = 1; p[i] = i; } for (int i = 1; i < n; ++i){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } int kekich = 0; cin >> k; for (int i = 1; i <= k; ++i){ cin >> zu[i] >> zu2[i]; zp[zu[i]].pb(mp(zu2[i], ++kekich)); zp[zu2[i]].pb(mp(zu[i], kekich)); } cin >> q; for (int i = 1; i <= q; ++i){ cin >> type[i]; cin >> uu[i] >> vv[i]; zp[uu[i]].pb(mp(vv[i], ++kekich)); zp[vv[i]].pb(mp(uu[i], kekich)); if (type[i] == 3){ cin >> t[i] >> t2[i]; } } dfs(); int lkek = 0; for (int i = 1; i <= k; ++i){ ++lkek; int lca = lc[lkek]; upd(zu[i], zu2[i], lca, 1); } for (int i = 1; i <= q; ++i){ ++lkek; if (type[i] == 1){ int lca = lc[lkek]; upd(uu[i], vv[i], lca, 1); } else if (type[i] == 2){ int lca = lc[lkek]; upd(uu[i], vv[i], lca, 0); } else{ lac = lc[lkek]; ll ans = calc2(uu[i], vv[i], t2[i]) - calc2(uu[i], vv[i], t[i] - 1); cout << ans << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...