oj.uz

Submission #557371

# Submission time Handle Problem Language Result Execution time Memory
557371 2022-05-05T08:30:59 Z FatihSolak Traffickers (RMI18_traffickers) C++17
20 / 100
 3500 ms 104752 KB 
#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++;
    par[v][0] = pr;
    for(auto u:adj[v]){
        if(u == pr)continue;
        dep[u] = dep[v] + 1;
        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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 50388 KB Output is correct
2 Correct 187 ms 52172 KB Output is correct
3 Correct 48 ms 52096 KB Output is correct

Subtask #2
5.0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3572 ms 67868 KB Time limit exceeded
2 Correct 2917 ms 66176 KB Output is correct
3 Execution timed out 3584 ms 67524 KB Time limit exceeded
4 Execution timed out 3580 ms 68064 KB Time limit exceeded
5 Execution timed out 3588 ms 67692 KB Time limit exceeded
6 Execution timed out 3595 ms 67776 KB Time limit exceeded
7 Execution timed out 3585 ms 67528 KB Time limit exceeded
8 Execution timed out 3589 ms 68260 KB Time limit exceeded
9 Execution timed out 3601 ms 68428 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3586 ms 103664 KB Time limit exceeded
2 Execution timed out 3594 ms 104368 KB Time limit exceeded
3 Execution timed out 3599 ms 103988 KB Time limit exceeded
4 Execution timed out 3582 ms 102908 KB Time limit exceeded
5 Execution timed out 3585 ms 102944 KB Time limit exceeded
6 Execution timed out 3557 ms 104568 KB Time limit exceeded
7 Execution timed out 3568 ms 104752 KB Time limit exceeded
8 Execution timed out 3581 ms 104332 KB Time limit exceeded