oj.uz

답안 #1106178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106178 2024-10-29T13:25:59 Z Whisper Traffickers (RMI18_traffickers) C++17
100 / 100
 994 ms 57928 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX                 30005
#define LOG                 15

int numNode, numQuery;
vector<int> G[MAX];

int up[MAX][LOG], depth[MAX];
int tin[MAX], tout[MAX], timeDfs = 0;
void pre_dfs(int u, int p = -1){
    tin[u] = ++timeDfs;
    for (int&v : G[u]) if(v ^ p){
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        for (int i = 1; i < LOG; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
        pre_dfs(v, u);
    }
    tout[u] = timeDfs;
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    int dis = depth[u] - depth[v];
    for (; dis > 0; dis ^= (dis & -dis)){
        int i = __builtin_ctz(dis & -dis);
        u = up[u][i];
    }
    if(u == v) return u;
    for (int i = LOG - 1; i >= 0; --i) if(up[u][i] != up[v][i]){
        u = up[u][i], v = up[v][i];
    }
    return up[u][0];
}

struct FenwickTree{
    vector<int> F;
    int n;
    void init(int _n = 0){
        this -> n = _n;
        F.resize(n + 5);
    }
    int low_bit (int p){
        return p & -p;
    }
    void upd(int p, int v){
        for (; p <= n; p += low_bit(p)) F[p] += v;
    }
    int ask(int p){
        int res = 0;
        for (; p > 0; p -= low_bit(p)) res += F[p];
        return res;
    }
    void upd(int l, int r, int v){
        upd(l, v); upd(r + 1, -v);
    }
} ft[21][21];

void add(int u, int v, int value){
    int pa = lca(u, v);
    vector<int> nodeu, nodev;
    while (u != pa){
        nodeu.emplace_back(u);
        u = up[u][0];
    }
    nodeu.emplace_back(pa);
    while (v != pa){
        nodev.emplace_back(v);
        v = up[v][0];
    }
    reverse(nodev.begin(), nodev.end());
    for (int&v : nodev) nodeu.emplace_back(v);

    int len = (int)nodeu.size();
    for (int i = 0; i < len; ++i){
        int u = nodeu[i];
        ft[len][i].upd(tin[u], tout[u], value);
    }
}

int ask(int u, int v, int T[]){
    int pa = lca(u, v);
    int ans = 0;
    for (int len = 1; len <= 20; ++len){
        for (int time = 0; time < len; ++time){
            int cover = ft[len][time].ask(tin[u]) + ft[len][time].ask(tin[v]) - ft[len][time].ask(tin[pa]) - ft[len][time].ask(tin[up[pa][0]]);
            if(T[1] - time < 0) continue;
            int cnt = (T[1] - time) / len + 1;
            if(T[0] - time - 1 >= 0){
                cnt -= (T[0] - time - 1) / len + 1;
            }
            ans += cnt * cover;
        }
    }
    return ans;
}
void process(void){
    cin >> numNode;
    for (int i = 1; i < numNode; ++i){
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    pre_dfs(1);
    FOR(i, 1, 20) REP(j, i) ft[i][j].init(numNode + 5);

    int k; cin >> k;
    for (int i = 1; i <= k; ++i){
        int u, v; cin >> u >> v;
        add(u, v, 1);
    }
    cin >> numQuery;
    for (int i = 1; i <= numQuery; ++i){
        int cmd; cin >> cmd;
        int u, v; cin >> u >> v;

        if(cmd == 1){
            add(u, v, 1);
        }
        if(cmd == 2){
            add(u, v, -1);
        }
        if(cmd == 3){
            int T[2]; cin >> T[0] >> T[1];
            cout << ask(u, v, T) << '\n';
        }
    }
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 5 ms 2896 KB Output is correct
3 Correct 4 ms 2896 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 20048 KB Output is correct
2 Correct 65 ms 18000 KB Output is correct
3 Correct 66 ms 19016 KB Output is correct
4 Correct 65 ms 19752 KB Output is correct
5 Correct 62 ms 19536 KB Output is correct
6 Correct 64 ms 22352 KB Output is correct
7 Correct 66 ms 22076 KB Output is correct
8 Correct 80 ms 22760 KB Output is correct
9 Correct 52 ms 22552 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 994 ms 57160 KB Output is correct
2 Correct 927 ms 57928 KB Output is correct
3 Correct 804 ms 57416 KB Output is correct
4 Correct 774 ms 56844 KB Output is correct
5 Correct 756 ms 56652 KB Output is correct
6 Correct 798 ms 57716 KB Output is correct
7 Correct 558 ms 57928 KB Output is correct
8 Correct 588 ms 57552 KB Output is correct