oj.uz

답안 #375246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375246 2021-03-09T05:15:54 Z ijxjdjd Traffickers (RMI18_traffickers) C++14
0 / 100
 3096 ms 107416 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] - 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--, 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7532 KB Output isn't correct
2 Incorrect 11 ms 9836 KB Output isn't correct
3 Incorrect 13 ms 9824 KB Output isn't correct

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 233 ms 39352 KB Output isn't correct
2 Incorrect 271 ms 36760 KB Output isn't correct
3 Incorrect 226 ms 38764 KB Output isn't correct
4 Incorrect 245 ms 39592 KB Output isn't correct
5 Incorrect 242 ms 39404 KB Output isn't correct
6 Incorrect 266 ms 39556 KB Output isn't correct
7 Incorrect 253 ms 39148 KB Output isn't correct
8 Incorrect 220 ms 39532 KB Output isn't correct
9 Incorrect 169 ms 39788 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2717 ms 106332 KB Output isn't correct
2 Incorrect 2811 ms 107128 KB Output isn't correct
3 Incorrect 2564 ms 106732 KB Output isn't correct
4 Incorrect 2819 ms 105824 KB Output isn't correct
5 Incorrect 3096 ms 105544 KB Output isn't correct
6 Incorrect 2696 ms 107244 KB Output isn't correct
7 Incorrect 2390 ms 107416 KB Output isn't correct
8 Incorrect 2325 ms 107100 KB Output isn't correct