Submission #287088

#TimeUsernameProblemLanguageResultExecution timeMemory
287088crossing0verTraffickers (RMI18_traffickers)C++17
15 / 100
2184 ms61572 KiB
#include<bits/stdc++.h> //#define int long long #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,MXN = 2*N; 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; int bit[21][21][N],sum[21][21][N]; void add(int k,int rem,int pos,int val) { for (;pos < MXN; pos += pos&-pos) bit[k][rem][pos]+=val; } int get(int k,int rem,int pos ) { int s = 0; for (;pos;pos-=pos&-pos) s += bit[k][rem][pos]; return s; } void add(int a,int b,int val) { int c = 0; int root = lca(a,b); int k = h[a] - h[root] + h[b] - h[root] + 1; while (a != root) { add(k,c,tin[a],val); add(k,c,tout[a],-val); sum[k][c][a] += val; c++; a = P[a][0]; } add(k,c,tin[root],val); add(k,c,tout[root],-val); sum[k][c][root] += val; c = k-1; while (b != root) { sum[k][c][b] += val; add(k,c,tin[b],val); add(k,c,tout[b],-val); 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]; } } int get(int k,int rem,int l,int r) { return get(k,rem,r) - get(k,rem,l-1); } main() { ios::sync_with_stdio(0); cin.tie(0); // freopen("01.in","r",stdin); // freopen("E.txt","w",stdout); 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,1); }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,1); }else if (tp == 2) { int a,b; cin >> a >> b; add(a,b,-1); }else { vi path; int u,v,t1,t2; cin >> u >> v >> t1 >> t2; int root = lca(u,v); ll ans = 0; for (int k = 1; k <= 20; k++) for (int rem = 0; rem < k; rem++) { int e = get(k,rem,tin[root],tin[u]); e += get(k,rem,tin[root],tin[v]); e -= sum[k][rem][root]; int b1 = t1; if ((b1%k) < rem) { b1 = b1 - (b1%k) + rem; } else if ((b1%k) > rem)b1 = b1- (b1%k) + rem + k; if (b1 <= t2) { ans += (t2 - b1 + k )/k*e; //e -= get() } } cout << ans <<'\n';continue; } //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) { for (auto j : s[i]) { int k = j.fi; int rem = j.se; int b1 = t1; if ((b1%k) < rem) { b1 = b1 - (b1%k) + rem; } else if ((b1%k) > rem)b1 = b1- (b1%k) + rem + k; if (b1 <= t2) { ans += (t2 - b1 + k )/k; } } }*/ } }

Compilation message (stderr)

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