Submission #315339

#	Time	Username	Problem	Language	Result	Execution time	Memory
315339		bigDuck	Traffickers (RMI18_traffickers)	C++14	100 / 100	2636 ms	456516 KiB

traffickers

#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, a[300010], q, l, r;
vector<int> g[30010];

int tmp=0;
bool vg[30010];
int anc[30010][21];
int ent[30010], ex[30010];


void dfs(int s){
vg[s]=true;
tmp++; ent[s]=tmp;
    for(auto 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];
            }
        }
    }
}
return;
}

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

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




int fw[2][200010][21][21];

int fw_q(int u, int i1, int i2, int ext){

int x=ex[u]+1;

int res=0;
    for(int i=100000ll-x+1; i>0; i-=(i&(-i))){
        res+=fw[ext][i][i1][i2]; //cout<<(i&(-i))<<" "<<flush;
    }
    //cout<<"x"<<flush;
return res;
}

void fw_u(int u, int i1, int i2, 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][i1][i2]+=upd;
}

}


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){
    cr=anc[cr][0];
    l++;
}
cr=v;
while(cr!=lca){
    cr=anc[cr][0];
    l++;
}

cr=u;
int t1=0;
while(cr!=lca){
    fw_u(cr, t1, l, 0, upd); fw_u(cr, t1, l, 1, upd); cnt[cr][t1][l]+=upd;
    t1++; cr=anc[cr][0];
}
fw_u(cr, t1, l, 0, upd); fw_u(cr, t1, l, 1, upd); cnt[cr][t1][l]+=upd;
cr=v;
t1=0;
while(cr!=lca){
    fw_u(cr, l-t1-1, l, 0, upd); fw_u(cr, l-t1-1, l, 1, upd); cnt[cr][l-t1-1][l]+=upd;
    t1++; cr=anc[cr][0];
}
//cout<<"bandit: "<<u<<" "<<v<<", period:"<<l<<"\n";
return;
}



int until_t(int res, int i1, int i2, int t){
return res*( ((i1<=t)?(1):(0))+max((t-i1)/i2, 0ll) );
}





int direct_branch(int u, int lca, int t1, int t2){
int res=0;

for(int i=0; i<=20; i++){
    for(int j=1; j<=20; j++){
        //cout<<"u:"<<u<<" , su="<<(fw_q(u, i, j, 1)-fw_q(u, i, j, 0))<<"... lca="<<lca<<", sl="<<(fw_q(lca, i, j, 1)-fw_q(lca, i, j, 0))<<"\n";
        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));

        res+=until_t(su-sl, i, j, t2)-until_t(su-sl, i, j, t1-1);
    }
}

//cout<<u<<" "<<lca<<" "<<res<<" t:"<<t1<<" "<<t2<<"q\n";
return res;
}



int query(int u, int v, int t1, int t2){
int res=0;
int lca=Lca(u, v);
//cout<<"nod:"<<u<<", "<<v<<" ; lca:"<<lca<<"\n";
// branch-ul lui u:
res+=direct_branch(u, lca, t1, t2);

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

//elimin repetarea lui lca:
for(int i=0; i<=20; i++){
    for(int j=1; j<=20; j++){
        res-=until_t(cnt[lca][i][j], i, j, t2)-until_t(cnt[lca][i][j], i, j, t1-1);
        res+=until_t(cnt[u][i][j], i, j, t2)-until_t(cnt[u][i][j], i, j, t1-1);
        res+=until_t(cnt[v][i][j], i, j, t2)-until_t(cnt[v][i][j], i, j, t1-1);
    }
}
return res;
}





int32_t main(){
INIT
cin>>n;
for(int i=1; i<=(n-1); 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);
}

/*for(int i=1; i<=n; i++){
    cout<<i<<"  ("<<ent[i]<<" "<<ex[i]<<") : ";
    for(int j:g[i]){
        cout<<j<<" ";
    }
    cout<<"\n";
}*/



cin>>q;
for(int i=1; i<=q ;i++){
    int u, v, t1, t2, tp;
    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";
    }
}


/*for(int i=1; i<=n; i++){
    for(int j=0; j<=19; j++){
        for(int f=1; f<=20; f++){
            int r1=fw_q(i, j, f, 1), r0=fw_q(i, j, f, 0);
            if( (r1>0) || (r0>0) ){cout<<"nod="<<i<<" i="<<j<<", j="<<f<<" r1:"<<r1<<" "<<"r0:"<<r0<<"\n";}
        }
    }
}*/


return 0;
}

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