Submission #872974

#	Time	Username	Problem	Language	Result	Execution time	Memory
872974		vjudge1	Traffickers (RMI18_traffickers)	C++17	15 / 100	986 ms	405168 KiB

traffickers

// #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")  
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define bit(a, i) ((a>>i)&1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int P = 31;
const int K = 400;
const ll inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9+7;
const int maxn = 5e4 + 10;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};

int n, k, q;
int p[maxn];
int lev[maxn];
int cnt[1000][maxn];
vector<int>g[maxn];

void dfs(int v, int pr){
    p[v] = pr; 
    lev[v] = lev[pr] + 1;
    for(int to: g[v]){
        if(to != pr) 
            dfs(to, v);
    }
}

void add(int u, int v, int x){
    vector<int>a, b;
    while(u != v){
        if(lev[u] >= lev[v]) {
            a.pb(u);
            u = p[u];
        } else {
            b.pb(v);
            v = p[v];
        }
    } a.pb(u);
    while(sz(b)){
        a.pb(b.back());
        b.pop_back();
    } int pos = 0;
    for(int t=0; t<1000; t++){
        cnt[t][a[pos++]]+=x;
        if(pos == sz(a)) pos = 0;
    }
}

int s(int l, int r, int v, int sum=0){
    for(int j=l; j<=r; j++) sum += cnt[j][v];
    return sum;
}

int get(int u, int v, int l, int r){
    vector<int>a, b;
    int sum = 0;
    while(u != v){
        if(lev[u] >= lev[v]) {
            sum += s(l, r, u);
            u = p[u];
        } else {
            sum += s(l, r, v);
            v = p[v];
        }
    } return sum + s(l, r, u);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    } cin >> k;
    dfs(1, 0);
    for(int i=1; i<=k; i++){
        int u, v;
        cin >> u >> v;
        add(u, v, 1);
    } cin >> q;
    for(int i=1; i<=q; i++){
        int tp, u, v;
        cin >> tp >> u >> v;
        if(tp == 1){
            add(u, v, 1);
        } else if(tp == 2) {
            add(u, v, -1);
        } else{
            int l, r; cin >> l >> r;
            cout << get(u, v, l, r) << "\n";
        }
    }
}   

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