#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;
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) {
for (auto j : s[i]) {
int k = j.fi;
int rem = j.se;
if (t1 + rem <= t2) {
ans += (t2 - (t1 + rem) + k )/k;
}
}
}
cout << ans <<'\n';
}
}
}
Compilation message
traffickers.cpp:81:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
81 | main() {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2560 KB |
Output isn't correct |
| 2 |
Incorrect |
29 ms |
3072 KB |
Output isn't correct |
| 3 |
Incorrect |
11 ms |
3072 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1288 ms |
8952 KB |
Output isn't correct |
| 2 |
Incorrect |
884 ms |
8440 KB |
Output isn't correct |
| 3 |
Incorrect |
1503 ms |
9064 KB |
Output isn't correct |
| 4 |
Incorrect |
1135 ms |
9208 KB |
Output isn't correct |
| 5 |
Incorrect |
971 ms |
8944 KB |
Output isn't correct |
| 6 |
Incorrect |
1022 ms |
8824 KB |
Output isn't correct |
| 7 |
Incorrect |
1179 ms |
8920 KB |
Output isn't correct |
| 8 |
Incorrect |
1651 ms |
9028 KB |
Output isn't correct |
| 9 |
Execution timed out |
3568 ms |
9072 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3561 ms |
45360 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3574 ms |
46500 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3571 ms |
45920 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3563 ms |
44920 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3587 ms |
44888 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3590 ms |
46048 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3588 ms |
46212 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3601 ms |
45612 KB |
Time limit exceeded |
