oj.uz

Submission #315373

# Submission time Handle Problem Language Result Execution time Memory
315373 2020-10-22T18:22:34 Z bigDuck Traffickers (RMI18_traffickers) C++14
100 / 100
 3143 ms 454084 KB 
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, k, q;
vector<int> g[30010];
int anc[30010][20];

int ent[30010], ex[30010];

int tmp=0;
bool vg[30010];

void dfs(int s){
vg[s]=true;
tmp++;ent[s]=tmp;
for(int u:g[s]){
    if(!vg[u]){
        anc[u][0]=s;
        dfs(u);
    }
}
tmp++; ex[s]=tmp;
return;
}

void binary_lifting(){
    for(int i=1; i<=19; i++){
        for(int j=1; j<=n; j++){
            if(anc[j][i-1]!=0 ){
                if(anc[anc[j][i-1]][i-1]!=0 ){
                    anc[j][i]=anc[anc[j][i-1] ][i-1];
                }
            }
        }
    }
}

bool is_ancestor(int u, int v){
return ( (ent[u]<=ent[v]) && (ex[u]>=ex[v] ) );
}

int Lca(int u, int v){
if(is_ancestor(u, v)){return u;}
int cr=u;
for(int j=19; j>=0; j--){
    if( (anc[cr][j]!=0) && (!is_ancestor(anc[cr][j], v)) ){
        cr=anc[cr][j];
    }
}
return anc[cr][0];
}

int fw[2][100010][21][21];

void fw_u(int u, int t1, int t2, int ext, int upd){
    int x;
    if(ext==1){
        x=ex[u];
    }
    else{
        x=ent[u];
    }
    for(int i=100000-x+1; i<=100000; i+=(i&(-i))){
        fw[ext][i][t1][t2]+=upd;
    }
    return;
}

int fw_q(int u, int t1, int t2, int ext){
//cout<<u<<" "<<ex[u]<<"\n";
int x=ex[u]+1;
int res=0;
    for(int i=100000-x+1; i>0; i-=(i&(-i))){
        res+=fw[ext][i][t1][t2];
    }
return res;
}

int cnt[30010][21][21];

void bandit(int u, int v, int upd){
int lca=Lca(u, v);

int l=1;
int cr=u;
while(cr!=lca){
    l++; cr=anc[cr][0];
}

cr=v;
while(cr!=lca){
    cr=anc[cr][0]; l++;
}

int t1=0;
cr=u;
while(cr!=lca){
    cnt[cr][t1][l]+=upd; fw_u(cr, t1, l, 1, upd);fw_u(cr, t1, l, 0, upd); cr=anc[cr][0]; t1++;
}

cnt[cr][t1][l]+=upd; fw_u(cr, t1, l, 1, upd); fw_u(cr, t1, l, 0, upd);

t1=0;
cr=v;
while(cr!=lca){
   cnt[cr][l-t1-1][l]+=upd; fw_u(cr, l-t1-1, l, 1, upd);fw_u(cr, l-t1-1, l, 0, upd); cr=anc[cr][0]; t1++;
}

return;
}

int until_t(int add,int t1, int t2, int t){
    return (  ( (t>=t1)?(add):(0)  )+max(0ll, add*( (t-t1)/t2 ) )   );
}

int btwn(int add, int i, int j, int t1, int t2){
    return until_t(add, i, j, t2)-until_t(add, i, j, t1-1);
}

int direct_branch(int u, int lca, int t1, int t2){
int res=0;
    for(int i=0; i<=19; i++){
        for(int j=1; j<=20; j++){
            int su=fw_q(u, i, j, 1)-fw_q(u, i, j, 0), sl=fw_q(lca, i, j, 1)-fw_q(lca, i, j, 0);
                    //cout<<(su-sl)<<" "<<u<<" "<<lca<<" "<<t1<<" "<<t2<<" "<<i<<" "<<j<<"\n";
            res+=btwn(su-sl, i, j, t1, t2 );
        }
    }
    return res;
}


int query(int u, int v, int t1, int t2){
int res=0;
int lca=Lca(u, v);
//branch u:
res+=direct_branch(u, lca, t1, t2);

//branchul 2:
res+=direct_branch(v, lca, t1, t2);

for(int i=0; i<=19; i++){
    for(int j=1; j<=20; j++){
        res-=btwn(cnt[lca][i][j], i, j, t1, t2);
        res+=btwn(cnt[u][i][j], i, j, t1, t2);
        res+=btwn(cnt[v][i][j], i, j, t1, t2);
    }
}
return res;
}

int32_t main(){
INIT
cin>>n;
for(int i=1; i<n; i++){
    int u, v;cin>>u>>v;g[u].pb(v); g[v].pb(u);
}
dfs(1);
binary_lifting();
cin>>k;
for(int i=1; i<=k; i++){
    int u, v; cin>>u>>v;
    bandit(u, v, 1);
}
cin>>q;
for(int i=1; i<=q; i++){
    int tp, u, v, t1, t2;
    cin>>tp>>u>>v;
    if(tp==1){
        bandit(u, v, 1);
    }
    if(tp==2){
        bandit(u, v, -1);
    }
    if(tp==3){
            cin>>t1>>t2;
        cout<<query(u, v, t1, t2)<<"\n";
    }
}

return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1664 KB Output is correct
2 Correct 35 ms 11904 KB Output is correct
3 Correct 33 ms 14080 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 123768 KB Output is correct
2 Correct 344 ms 121976 KB Output is correct
3 Correct 331 ms 106872 KB Output is correct
4 Correct 353 ms 127352 KB Output is correct
5 Correct 356 ms 130584 KB Output is correct
6 Correct 353 ms 129272 KB Output is correct
7 Correct 351 ms 124920 KB Output is correct
8 Correct 335 ms 112632 KB Output is correct
9 Correct 314 ms 107384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3022 ms 429728 KB Output is correct
2 Correct 3043 ms 383644 KB Output is correct
3 Correct 2891 ms 351632 KB Output is correct
4 Correct 3043 ms 454084 KB Output is correct
5 Correct 3143 ms 444724 KB Output is correct
6 Correct 2984 ms 363632 KB Output is correct
7 Correct 2744 ms 319736 KB Output is correct
8 Correct 2791 ms 319608 KB Output is correct