제출 #557374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557374		FatihSolak	Traffickers (RMI18_traffickers)	C++17	100 / 100	1541 ms	104460 KiB

traffickers

#include <bits/stdc++.h>
#define N 30005
#define K 20
#define M 15
using namespace std;
vector<int> adj[N];
int par[N][M];
int dep[N];
int timer = 1;
int tin[N],tout[N];
int cnt[N][K+1][K];
struct BIT{
    vector<int> bit;
    int n;
    BIT(){
        n = N;
        bit.assign(n,0);
    }
    void upd(int pos,int val){
        for(;pos < n;pos += pos & -pos){
            bit[pos] += val;
        }
    }
    int get(int pos){
        int ret = 0;
        for(;pos > 0;pos -= pos & -pos){
            ret += bit[pos];
        }
        return ret;
    }
    void upd(int l,int r,int val){
        upd(l,val);
        upd(r+1,-val);
    }
}bt[K+1][K];
void dfs(int v,int pr){
    tin[v] = timer++;
    dep[v] = dep[pr] + 1;
    par[v][0] = pr;
    for(auto u:adj[v]){
        if(u == pr)continue;
        dfs(u,v);
    }
    tout[v] = timer-1;
}
vector<int> get_path(int u,int v){
    vector<int> v1,v2;
    v1.push_back(u);
    while(tin[v] < tin[u] || tout[u] < tin[v]){
        u = par[u][0];
        v1.push_back(u);
    }
    while(v != u){
        v2.push_back(v);
        v = par[v][0];
    }
    reverse(v2.begin(),v2.end());
    for(auto c:v2){
        v1.push_back(c);
    }
    return v1;
}
int lca(int a,int b){
    if(dep[a] < dep[b])
        swap(a,b);
    for(int i = M-1;i>=0;i--){
        if(dep[par[a][i]] >= dep[b]){
            a = par[a][i];
        }
    }
    if(a == b)
        return a;
    for(int i =M-1;i>=0;i--){
        if(par[a][i] != par[b][i]){
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}
void trafficker(int u,int v,int val){
    auto path = get_path(u,v);
    int sz = path.size();
    for(int i = 0;i<sz;i++){
        cnt[path[i]][sz][i] += val;
        bt[sz][i].upd(tin[path[i]],tout[path[i]],val);
    }
}
long long get(int a,int t){
    long long ret = 0;
    for(int i = 1;i<=K;i++){
        for(int j = 0;j<i;j++){
            long long time = (t + 1) / i + (j < (t+1)%i);
            ret += (time) * bt[i][j].get(tin[a]);
        }
    }
    return ret;
}
long long get2(int a,int t){
    long long ret = 0;
    for(int i = 1;i<=K;i++){
        for(int j = 0;j<i;j++){
            long long time = (t + 1) / i + (j < (t+1)%i);
            ret += (time) * cnt[a][i][j];
        }
    }
    return ret;
}
long long get(int u,int v,int t){
    if(t == -1)return 0;
    int lc = lca(u,v);
    long long ret = get(u,t) + get(v,t) - 2*get(lc,t) + get2(lc,t);
    // long long ret = 0;
    // for(auto x:get_path(u,v)){
    //     ret += get2(x,t);
    // }
    return ret;
}
void solve(){
    int n;
    cin >> n;
    for(int i = 1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    for(int j = 1;j<M;j++){
        for(int i = 1;i<=n;i++){
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    int k;
    cin >> k;
    for(int i = 1;i<=k;i++){
        int u,v;
        cin >> u >> v;
        trafficker(u,v,1);
    }
    int q;
    cin >> q;
    while(q--){
        int type;
        cin >> type;
        if(type < 3){
            int u,v;
            cin >> u >> v;
            trafficker(u,v,(type == 1?1:-1));
        }
        if(type == 3){
            int u,v,t1,t2;
            cin >> u >> v >> t1 >> t2;
            cout << get(u,v,t2) - get(u,v,t1-1) << endl;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl <<fixed << setprecision(2) << 1000.0 * clock() /CLOCKS_PER_SEC << " milliseconds." << endl;
    #endif
}

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