oj.uz

Submission #310582

# Submission time Handle Problem Language Result Execution time Memory
310582 2020-10-07T12:19:55 Z bigDuck Traffickers (RMI18_traffickers) C++14
15 / 100
 3500 ms 107128 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, a[300010], q, l, r;
vector<int> g[30010];
int ent[30010];
int ex[30010];
int par[30010];
int dp[30010][21][21];


int tmp=1;
bool v[30010];
void tour(int s){
    v[s]=true;
    for(auto u:g[s]){
        if(!v[u]){
            tmp++; ent[u]=tmp;
            par[u]=s;
            tour(u);
        }
    }
    tmp++;
    ex[s]=tmp;
    v[s]=false;
}



void ins(int &u, int &v){
    int l1=0, l2=0;
    int cr=u;
    if(u==v){
        dp[u][1][1]++; return;
    }
    while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) ||(cr==v)  )  ){
        cr=par[cr]; l1++; //cout<<ent[cr]<<" "<<flush;
    }
    cr=v;
    while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) || (cr==u) )  ){
        cr=par[cr]; l2++;
    }
    int l=(l1+l2+1);
    dp[cr][l1+1][l]++;
    l1=1;
    cr=u;
    while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) ||(cr==v) ) ){
        dp[cr][l1][l]++;
         l1++; cr=par[cr];
    }
    l2=0;
    cr=v;
    while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) ||(cr==u) ) ){
        dp[cr][l-l2][l]++; l2++; cr=par[cr];
    }
    return;
}

void ers(int &u, int &v){
        int l1=0, l2=0;
    int cr=u;
    if(u==v){dp[u][1][1]--; return;}
    while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) ||(cr==v) )  ){
        cr=par[cr]; l1++;
    }
    cr=v;
    while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) || (cr==u) )  ){
        cr=par[cr]; l2++;
    }
    int l=(l1+l2+1);
    dp[cr][l1+1][l]--;
    l1=1;
    cr=u;
    while(!( ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) || (cr==v) ) ){
        dp[cr][l1][l]--;
         l1++; cr=par[cr];
    }
    l2=0;
    cr=v;
    while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) || (cr==u) ) ){
        dp[cr][l-l2][l]--; l2++; cr=par[cr];
    }
    return;
}




int query(int &u, int &v,int t1, int t2){
    int res=0;
    int cr=u;
    while(!(  ((ent[cr]<ent[v]) && (ex[cr]>ex[v])) || (cr==v) ) ){
        for(int i=1; i<=20; i++){
            for(int j=1; j<=20; j++){
                res+=( dp[cr][i][j]*(( ( max(((t2-i)/j), 0ll)+((t2>=i)?1ll:0ll) )-( max(((t1-1-i)/j), 0ll)+((t1>i)?1ll:0ll) )  )  )  );
            }
        }
        cr=par[cr];
    }

        for(int i=1; i<=20; i++){
            for(int j=1; j<=20; j++){
                res+=( dp[cr][i][j]*(( ( max(((t2-i)/j), 0ll)+((t2>=i)?1ll:0ll) )-( max(((t1-1-i)/j ), 0ll)+((t1>i)?1ll:0ll) )  )  )  );
            }
        }

    cr=v;
    while(!( ((ent[cr]<ent[u]) && (ex[cr]>ex[u])) || (cr==u) ) ){
        for(int i=1; i<=20; i++){
            for(int j=1; j<=20; j++){
                res+=( dp[cr][i][j]*(( ( max(((t2-i)/(j) ), 0ll)+((t2>=i)?1ll:0ll) )-( max(((t1-1-i)/j), 0ll)+((t1>i)?1ll:0ll) )  )  )  );
            }
        }
        cr=par[cr];
    }
    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);
}
ent[1]=0;
tour(1);
cin>>k;
for(int i=1; i<=k; i++){
    int u, v; cin>>u>>v;
    ins(u, v);
}
cin>>q;

while(q--){
    int o; cin>>o;
    if(o==1){
        int u, v; cin>>u>>v;
        ins(u, v);
    }
    if(o==2){
        int u, v; cin>>u>>v;
        ers(u, v);
    }
    if(o==3){
            int u, v, t1, t2; cin>>u>>v>>t1>>t2; 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 8 ms 1408 KB Output is correct
2 Correct 1322 ms 4772 KB Output is correct
3 Correct 207 ms 4348 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3563 ms 33432 KB Time limit exceeded
2 Execution timed out 3589 ms 28688 KB Time limit exceeded
3 Execution timed out 3575 ms 34204 KB Time limit exceeded
4 Execution timed out 3580 ms 32872 KB Time limit exceeded
5 Execution timed out 3580 ms 31352 KB Time limit exceeded
6 Execution timed out 3554 ms 31812 KB Time limit exceeded
7 Execution timed out 3583 ms 32256 KB Time limit exceeded
8 Execution timed out 3586 ms 35756 KB Time limit exceeded
9 Execution timed out 3562 ms 36352 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3572 ms 105848 KB Time limit exceeded
2 Execution timed out 3594 ms 106616 KB Time limit exceeded
3 Execution timed out 3586 ms 106616 KB Time limit exceeded
4 Execution timed out 3573 ms 102376 KB Time limit exceeded
5 Execution timed out 3577 ms 99856 KB Time limit exceeded
6 Execution timed out 3577 ms 106744 KB Time limit exceeded
7 Execution timed out 3531 ms 107128 KB Time limit exceeded
8 Execution timed out 3535 ms 106872 KB Time limit exceeded