Submission #375275

#	Time	Username	Problem	Language	Result	Execution time	Memory
375275		ijxjdjd	Traffickers (RMI18_traffickers)	C++14	100 / 100	3067 ms	104984 KiB

traffickers

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = 30000;
const int MAXK = 15;
const int MAXD = 20;

struct fenwick {
    int fen[2*MAXN];
    int reg[2*MAXN];
    void add(int val, int id) {
        reg[id]+=val;
        for (;id<2*MAXN;id=(id|(id+1))) {
            fen[id] += val;
        }
    }
    int sm(int id) {
        int res = 0;
        for (;id>=0;id=(id&(id+1)) - 1) {
            res += fen[id];
        }
        return res;
    }
};

fenwick fens[MAXD+1][MAXD+1];

int depth[MAXN];
int timer = 0;
int tin[MAXN];
int tout[MAXN];
vector<int> adj[MAXN];
int up[MAXN][MAXK];
void root(int n, int p, int d) {
    up[n][0] = p;
    depth[n] = d;
    for (int i = 1; i < MAXK; i++) {
        up[n][i] = up[up[n][i-1]][i-1];
    }
    tin[n] = timer++;
    for (int e : adj[n]) {
        if (e != p) {
            root(e, n, d+1);
        }
    }
    tout[n] = timer++;
}
bool is_ancestor(int a, int b) {
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int u, int v) {
    if (is_ancestor(u, v)) {
        return u;
    }
    else if (is_ancestor(v, u)) {
        return v;
    }
    else {
        for (int k = MAXK-1; k >= 0; k--) {
            if (!is_ancestor(up[u][k], v)) {
                u = up[u][k];
            }
        }
        return up[u][0];
    }
}
void upd(int cyc, int offset, int n, bool add) {
    if (add) {
        fens[cyc][offset].add(1, tin[n]);
        fens[cyc][offset].add(-1, tout[n]);
    }
    else {
        fens[cyc][offset].add(-1, tin[n]);
        fens[cyc][offset].add(1, tout[n]);
    }
}
ll calc(ll t, int u, int v, int lc) {
    if (t < 0) {
        return 0;
    }
    ll res = 0;
    for (ll cyc = 1; cyc <= MAXD; cyc++) {
        for (ll offset = 0; offset < cyc; offset++) {
            ll tp = fens[cyc][offset].sm(tin[u]) + fens[cyc][offset].sm(tin[v]) - 2*fens[cyc][offset].sm(tin[lc]) + fens[cyc][offset].reg[tin[lc]];
            if (offset <= t) {
                res += tp*((t - offset)/cyc + 1);
            }
        }
    }
    return res;
}
void chgCyc(int u, int v, bool add) {
    int lc = lca(u, v);
    int cyc = depth[u] + depth[v] - 2*depth[lc] + 1;
    int cnt = 0;
    while (u != lc) {
        upd(cyc, cnt++, u, add);
        u = up[u][0];
    }
    upd(cyc, cnt, u, add);
    cnt = cyc-1;
    while (v != lc) {
        upd(cyc, cnt--, v,add);
        v = up[v][0];
    }
}
int main() {
//    freopen("input.in", "r", stdin);
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	FR(i, N-1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
	}
	root(0, 0, 0);
	int K;
	cin >> K;
	FR(i, K) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        chgCyc(u, v, true);
	}
	int Q;
	cin >> Q;
	FR(iter, Q) {
        int id, u, v;
        cin >> id >> u >> v;
        u--, v--;
        if (id == 1) {
            chgCyc(u, v, true);
        }
        else if (id == 2) {
            chgCyc(u, v, false);
        }
        else if (id == 3) {
            ll t1, t2;
            int lc = lca(u, v);
            cin >> t1 >> t2;
            cout << calc(t2, u, v, lc) - calc(t1-1, u, v, lc) << '\n';
        }
	}
	return 0;
}

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