oj.uz

Submission #375235

# Submission time Handle Problem Language Result Execution time Memory
375235 2021-03-09T05:04:18 Z ijxjdjd Traffickers (RMI18_traffickers) C++14
0 / 100
 38 ms 11500 KB 
#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 = 2; cyc <= MAXD; cyc++) {
        for (ll offset = 0; offset < cyc; offset++) {
            ll tp = fens[cyc][offset].sm(tin[u]) + fens[cyc][offset].sm(tin[v]);
            tp -= fens[cyc][offset].reg[tin[lc]];
            if (lc != 0) {
                tp -= 2*fens[cyc][offset].sm(tin[up[lc][0]]);
            }
            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] - 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--, u,add);
        v = up[v][0];
    }
}
int main() {
	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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 2284 KB Execution killed with signal 11
2 Runtime error 15 ms 2284 KB Execution killed with signal 11
3 Runtime error 13 ms 2156 KB Execution killed with signal 11

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 4716 KB Execution killed with signal 11
2 Runtime error 20 ms 4332 KB Execution killed with signal 11
3 Runtime error 19 ms 5228 KB Execution killed with signal 11
4 Runtime error 19 ms 4844 KB Execution killed with signal 11
5 Runtime error 22 ms 4716 KB Execution killed with signal 11
6 Runtime error 20 ms 4844 KB Execution killed with signal 11
7 Runtime error 19 ms 4716 KB Execution killed with signal 11
8 Runtime error 20 ms 4972 KB Execution killed with signal 11
9 Runtime error 20 ms 5100 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 9836 KB Execution killed with signal 11
2 Runtime error 36 ms 11244 KB Execution killed with signal 11
3 Runtime error 37 ms 10604 KB Execution killed with signal 11
4 Runtime error 32 ms 9068 KB Execution killed with signal 11
5 Runtime error 31 ms 8684 KB Execution killed with signal 11
6 Runtime error 36 ms 11116 KB Execution killed with signal 11
7 Runtime error 36 ms 11500 KB Execution killed with signal 11
8 Runtime error 38 ms 10732 KB Execution killed with signal 11