Submission #1118791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118791		Bula	Traffickers (RMI18_traffickers)	C++17	100 / 100	1096 ms	66044 KiB

traffickers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7, N = 3e4 + 5, LOG = 16;
vector<int> adj[N], pth;
int s[N], e[N], depth[N], par[N];
int timer = 0;
void dfs(int v, int p){
    s[v] = ++timer; par[v] = p;
    for(auto x : adj[v]){
        if(x == p) continue;
		depth[x] = depth[v] + 1;
		dfs(x, v);
    }
    e[v] = timer;
}
int et[2 * N], lg[2 * N], tin[N];
pair<int, int> st[LOG + 1][2 * N];
void dfs1(int v, int p) {
	et[++timer] = v;
	tin[v] = timer;
	for(int u : adj[v]){
		if (u == p) continue;
		dfs1(u, v);
		et[++timer] = v;
	}
}
pair<int, int> rmq(int l, int r){
	int i = lg[r - l + 1];
	return min(st[i][l], st[i][r - (1 << i) + 1]);
}
int lca(int u, int v){
	if(tin[u] > tin[v]) swap(u, v);
	return rmq(tin[u], tin[v]).second;
}
int fenwick[N][21][21] = {};
int sum(int r, int i, int k) {
    int res = 0;
    while (r >= 0) {
        res += fenwick[r][i][k];
        r = (r & (r + 1)) - 1;
    }
    return res;
}
 
int get(int l, int r, int i, int k) {
    return sum(r, i, k) - sum(l - 1, i, k);
}
 
void inc(int j, int delta, int i, int k) {
    while (j < N) {
        fenwick[j][i][k] += delta;
        j |= j + 1;
    }
}
int Get(int u, int v, int i, int k){
    int x = lca(u, v);
    return get(1LL, s[u], i, k) + get(1LL, s[v], i, k) - get(1LL, s[x], i, k) - get(1LL, s[par[x]], i, k);
}
void upd(int v, int x, int i, int k){
	inc(s[v], x, i, k);
	inc(e[v] + 1, -x, i, k);
}
vector<int> path(int u, int v){
    int x = lca(u, v), a = u, b = v;
	vector<int> p;
	while(a != x){
		p.push_back(a);
		a = par[a];
	}
	p.push_back(x);
	vector<int> q;
	while(b != x){
		q.push_back(b);
		b = par[b];
	}
	reverse(q.begin(), q.end());
	for(auto k : q) p.push_back(k);
    return p;
}
void add(int u, int v){
    pth = path(u, v);
    int k = pth.size();
    for(int i = 0; i < k; i++){
        upd(pth[i], 1, i, k);
    }
}
void del(int u, int v){
    pth = path(u, v);
    int k = pth.size();
    for(int i = 0; i < k; i++){
        upd(pth[i], -1, i, k);
    }
}
ll calc(int i, int k, int t1, int t2){
    t1--;
    ll val1 = max(0, (t2 + k - i) / k);
    ll val2 = max(0, (t1 + k - i) / k);
    val1 -= val2;
    return val1;
}
void query(int u, int v, int t1, int t2){
    ll ans = 0;
    for(int i = 0; i <= 20; i++){
        for(int k = 1; k <= 20; k++){
            ans += 1LL * calc(i, k, t1, t2) * Get(u, v, i, k);
        }
    }
    cout << ans << '\n';
}
main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int tt = 1; //cin >> tt;
    while(tt--){
        int n;
        cin >> n;
        for(int i = 1; i <= n - 1; i++){
            int x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        dfs(1, 0); timer = 0; dfs1(1, 0);
	    for(int i = 1; i <= 2 * n; i++) st[0][i] = {depth[et[i]], et[i]};
	    for(int i = 1; i <= LOG; i++){
            for(int j = 1; j + (1 << i) - 1 <= 2 * n; j++){
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
        lg[1] = 0;
        for(int i = 2; i <= 2 * n; i++) lg[i] = lg[i / 2] + 1;
        int k;
        cin >> k;
        for(int i = 0; i < k; i++){
            int x, y;
            cin >> x >> y;
            add(x, y);
        }
        int q;
        cin >> q;
        while(q--){
            int t;
            cin >> t;
            if(t == 1){
                int x, y;
                cin >> x >> y;
                add(x, y);
            }else if(t == 2){
                int x, y;
                cin >> x >> y;
                del(x, y);
            }else{
                int x, y, t1, t2;
                cin >> x >> y >> t1 >> t2;
                query(x, y, t1, t2);
            }
        }
    }
}

Compilation message (stderr)

traffickers.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main(){
      | ^~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40