oj.uz

Submission #872973

# Submission time Handle Problem Language Result Execution time Memory
872973 2023-11-14T08:07:30 Z vjudge1 Traffickers (RMI18_traffickers) C++17
15 / 100
 35 ms 14684 KB 
// #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[20][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<=10; 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 10584 KB Execution killed with signal 11
2 Runtime error 8 ms 10328 KB Execution killed with signal 11
3 Runtime error 9 ms 11100 KB Execution killed with signal 11
4 Runtime error 9 ms 10844 KB Execution killed with signal 11
5 Runtime error 9 ms 10484 KB Execution killed with signal 11
6 Runtime error 11 ms 10640 KB Execution killed with signal 11
7 Runtime error 9 ms 10588 KB Execution killed with signal 11
8 Runtime error 9 ms 10844 KB Execution killed with signal 11
9 Runtime error 9 ms 10844 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 13552 KB Execution killed with signal 11
2 Runtime error 31 ms 14684 KB Execution killed with signal 11
3 Runtime error 31 ms 13916 KB Execution killed with signal 11
4 Runtime error 29 ms 12884 KB Execution killed with signal 11
5 Runtime error 35 ms 12628 KB Execution killed with signal 11
6 Runtime error 32 ms 14528 KB Execution killed with signal 11
7 Runtime error 30 ms 14672 KB Execution killed with signal 11
8 Runtime error 30 ms 14172 KB Execution killed with signal 11