Submission #899798

#	Time	Username	Problem	Language	Result	Execution time	Memory
899798		Cookie	Traffickers (RMI18_traffickers)	C++14	100 / 100	1123 ms	56016 KiB

traffickers

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, 0, -1, 0};
const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7;
const int mxn = 3e4 + 69, mxq = 1e5 + 5, sq = 500, mxv = 2e7 + 5;
//const int base = (1 <<18);
const int inf = 1e9 + 5, neg = -69420;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int x[9] = {0, 1, 1, -1, -1, 2, -2, 2, -2};
//const inty[9] = {0, 2, -2, 2, -2, 1, 1, -1, -1};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int n, k, q;
vt<int>adj[mxn + 1];
int tin[mxn + 1], tout[mxn + 1], dep[mxn + 1], up[mxn + 1][17], tt = 0;
struct BIT{
    int bit[mxn + 1];
    void upd(int p, int v){
        while(p <= n){
            bit[p] += v; p += p & (-p);
        }
    }
    int get(int p){
        int ans = 0;
        while(p){
            ans += bit[p]; p -= p & (-p);
        }
        return(ans);
    }
};
BIT bit[21][21];
void dfs(int s, int pre){
    tin[s] = ++tt;
    for(auto v: adj[s]){
        if(v != pre){
            up[v][0] = s;  dep[v] = dep[s] + 1;
            dfs(v, s);
        }
    }
    tout[s] = tt;
}
int lca(int u, int v){
    if(dep[u] < dep[v])swap(u, v);
    int k = dep[u] - dep[v];
    forr(i, 0, 17){
        if(k & (1 << i))u = up[u][i];
    }
    if(u == v)return(u);
    dorr(i, 16, 0){
        if(up[u][i] != up[v][i]){
            u = up[u][i]; v = up[v][i];
        }
    }
    return(up[u][0]);
}
void upd(int u, int v, int type){
    int lc = lca(u, v);
    vt<int>pathu, pathv;
    int remu = u, remv = v;
 
    while(u != lc){
 
        pathu.pb(u); u = up[u][0];
    }
    while(v != lc){
        pathv.pb(v); v = up[v][0];
    }
 
    pathu.pb(lc);
    reverse(ALL(pathv));
    for(auto i: pathv)pathu.pb(i);
    int len = sz(pathu);
    assert(len <= 20);
    
    for(int i = 0; i < sz(pathu); i++){
        
        //cout << pathu[i] << " " << tin[pathu[i]] << "\n";
        bit[len][i].upd(tin[pathu[i]], 1 * type); bit[len][i].upd(tout[pathu[i]] + 1, -1 * type);
    }
    
 
}
ll solve(int u, int v, ll t1,ll t2){
    int lc = lca(u, v);
    ll ans = 0;
    for(int i = 1; i <= 20; i++){
        for(int j = 0; j < i; j++){
            ll cntver = bit[i][j].get(tin[u]) + bit[i][j].get(tin[v]) - bit[i][j].get(tin[lc]) - bit[i][j].get(tin[up[lc][0]]);
          if(t2 - j < 0)continue;
            ll cnt = (t2 - j) / i + 1;
            if(t1 - 1 - j >= 0){
                cnt -= (t1 - 1 - j) / i + 1;
            }
            //cout << cnt << " ";
            ans += cnt * cntver;
        }
    }
    return(ans);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("COLLEGE.INP", "r", stdin);
    //freopen("COLLEGE.OUT", "w", stdout);
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    dfs(1, -1);
    for(int i = 1; i < 16; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    cin >> k;
    for(int i = 0; i < k; i++){
        int u, v; cin >> u >> v;
        upd(u, v, 1);
    }
 
    cin >> q;
    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            int u, v; cin >> u >> v; upd(u, v, 1);
        }else if(idq == 2){
            int u, v; cin >> u >> v; upd(u, v, -1);
        }else{
            int u, v, t1, t2; cin >> u >> v >> t1 >> t2;
            cout << solve(u, v, t1, t2) << "\n";
        }
 
    }
 
    return(0);
}

Compilation message (stderr)

traffickers.cpp: In function 'void upd(int, int, int)':
traffickers.cpp:80:9: warning: unused variable 'remu' [-Wunused-variable]
   80 |     int remu = u, remv = v;
      |         ^~~~
traffickers.cpp:80:19: warning: unused variable 'remv' [-Wunused-variable]
   80 |     int remu = u, remv = v;
      |                   ^~~~

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