oj.uz

답안 #557369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557369 2022-05-05T08:24:08 Z FatihSolak Traffickers (RMI18_traffickers) C++17
35 / 100
 1540 ms 104556 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][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);
    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
10.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 50420 KB Output is correct
2 Correct 25 ms 52064 KB Output is correct
3 Incorrect 24 ms 51940 KB Output isn't correct

Subtask #2
20.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 67356 KB Output is correct
2 Correct 110 ms 65632 KB Output is correct
3 Incorrect 156 ms 66996 KB Output isn't correct
4 Incorrect 132 ms 67452 KB Output isn't correct
5 Incorrect 156 ms 67148 KB Output isn't correct
6 Incorrect 121 ms 67312 KB Output isn't correct
7 Correct 136 ms 66992 KB Output is correct
8 Incorrect 121 ms 67640 KB Output isn't correct
9 Correct 128 ms 67788 KB Output is correct

Subtask #3
5.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1540 ms 103700 KB Output isn't correct
2 Incorrect 1375 ms 104492 KB Output isn't correct
3 Incorrect 1292 ms 104184 KB Output isn't correct
4 Incorrect 1317 ms 103332 KB Output isn't correct
5 Incorrect 1408 ms 103132 KB Output isn't correct
6 Incorrect 1263 ms 104332 KB Output isn't correct
7 Incorrect 1197 ms 104556 KB Output isn't correct
8 Correct 1386 ms 104264 KB Output is correct