Submission #287053

#TimeUsernameProblemLanguageResultExecution timeMemory
287053crossing0verTraffickers (RMI18_traffickers)C++17
0 / 100
3589 ms35124 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define pii pair<int,int> #define vi vector<int> #define fi first #define se second #define all(x) (x).begin(),(x).end() using namespace std; const int N = 3e4+5; vi adj[N]; int n,k,q,tin[N],tout[N],timer,P[N][18],h[N]; void dfs(int v,int p) { P[v][0] = p; h[v] = h[p] + 1; tin[v] = ++timer; for (int h = 1; h < 18; h++) P[v][h] = P[ P[v][h-1] ][h-1]; for (int i : adj[v]) { if (i != p) dfs(i,v); } tout[v] = ++timer; } bool isp(int a,int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } int lca(int a,int b) { if (isp(a,b)) return a; if (isp(b,a)) return b; for (int h = 17; h >= 0; h--) if (!isp(P[a][h],b)) a = P[a][h]; return P[a][0]; } multiset<pii> s[N]; map<pii,int> mp; void add(int a,int b) { int root = lca(a,b); int k = h[a] - h[root] + h[b] - h[root] + 1; int c = 0; while (a != root) { s[a].insert({k,c}); c++; a = P[a][0]; } s[root].insert({k,c}); c = k-1; while (b != root) { s[b].insert({k,c}); c--; b = P[b][0]; } } void erase(int a,int b) { mp[{a,b}]--; if (mp[{a,b}] == 0) mp.erase({a,b}); int root = lca(a,b); int k = h[a] - h[root] + h[b] - h[root] + 1; int c = 0; while (a != root) { s[a].erase(s[a].find(make_pair(k,c))); c++; a = P[a][0]; } // c++; s[root].erase(s[root].find({k,c})); c = k-1; while (b != root) { s[b].erase(s[b].find(make_pair(k,c))); c--; b = P[b][0]; } } main() { ios::sync_with_stdio(0); cin.tie(0); tout[0] = 1000000000; cin >> n; for (int i = 1 ; i < n; i++) { int a,b; cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } dfs(1,0); cin >> k; for (int i = 1; i <= k; i++) { int a,b; cin >> a >> b; mp[{a,b}]++; add(a,b); }cin >> q; for (int y = 1; y <= q; y++) { int tp; cin >> tp; if (tp == 1) { int a,b; cin >> a >> b; mp[{a,b}]++; add(a,b); }else if (tp == 2) { int a,b; cin >> a >> b; erase(a,b); }else { vi path; int u,v,t1,t2; cin >> u >> v >> t1 >> t2; int root = lca(u,v); //cout <<root<<"E\n"; while (u != root) { path.pb(u); u = P[u][0]; } while (v != root) { path.pb(v); v = P[v][0]; } if (root) path.pb(root); ll ans = 0; for (int i : path) { // cout << i <<"s "; // cout << i <<" "; for (auto j : s[i]) { // cout << "Q "<<j.fi<<"S "; //cout << j.fi <<' '<< j.se <<'s'; int k = j.fi; int rem = j.se; if (t1 + rem <= t2) { ans += (t2 - (t1 + rem) + k )/k; } } } cout << ans <<'\n'; } } }

Compilation message (stderr)

traffickers.cpp:80:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main() {
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...