Submission #1118603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118603		Bula	Traffickers (RMI18_traffickers)	C++17	70 / 100	3575 ms	60336 KiB

traffickers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7, N = 3e4 + 5, LOG = 20;
vector<int> adj[N];
int s[N], e[N], depth[N], up[N][LOG];
int timer = 0;
void dfs(int v, int p){
    s[v] = ++timer;
    for(auto x : adj[v]){
        if(x == p) continue;
		up[x][0] = v; depth[x] = depth[v] + 1;
        for(int j = 1; j < LOG; j++){
            up[x][j] = up[up[x][j - 1]][j - 1];
        }
		dfs(x, v);
    }
    e[v] = timer;
}
int lca(int u, int v){
	if(depth[u] < depth[v]) swap(u, v);
    int k = depth[u] - depth[v];
	for(int j = LOG - 1; j >= 0; j--){
        if(k & (1 << j)) u = up[u][j];
    }
    if(u == v) return v;
    for(int j = LOG - 1; j >= 0; j--){
        if(up[u][j] != up[v][j]){
            u = up[u][j]; v = up[v][j];
        }
    }
    return up[u][0];
}
int fenwick[N][LOG + 1][LOG + 1] = {};
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[up[x][0]], 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 = up[a][0];
	}
	p.push_back(x);
	vector<int> q;
	while(b != x){
		q.push_back(b);
		b = up[b][0];
	}
	reverse(q.begin(), q.end());
	for(auto k : q) p.push_back(k);
    return p;
}
void add(int u, int v){
    vector<int> p = path(u, v);
    int k = p.size();
    for(int i = 0; i < k; i++){
        upd(p[i], 1, i, k);
    }
}
void del(int u, int v){
    vector<int> p = path(u, v);
    int k = p.size();
    for(int i = 0; i < k; i++){
        upd(p[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){
    vector<int> p = path(u, v);
    ll ans = 0;
//    for(auto x : p){
//        for(int i = 0; i <= LOG; i++){
//            for(int k = 1; k <= LOG; k++){
//                ans += calc(i, k, t1, t2) * f[x][i][k];
//            }
//        }
//    }
    for(int i = 0; i <= LOG; i++){
        for(int k = 1; k <= LOG; 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);
        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:117:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  117 | main(){
      | ^~~~

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