oj.uz

Submission #872974

# Submission time Handle Problem Language Result Execution time Memory
872974 2023-11-14T08:12:59 Z vjudge1 Traffickers (RMI18_traffickers) C++17
15 / 100
 986 ms 405168 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[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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 197456 KB Output is correct
2 Correct 26 ms 197492 KB Output is correct
3 Correct 24 ms 197456 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 ms 401364 KB Execution killed with signal 11
2 Runtime error 254 ms 401228 KB Execution killed with signal 11
3 Runtime error 254 ms 401824 KB Execution killed with signal 11
4 Runtime error 249 ms 401660 KB Execution killed with signal 11
5 Runtime error 230 ms 401488 KB Execution killed with signal 11
6 Runtime error 246 ms 401748 KB Execution killed with signal 11
7 Runtime error 253 ms 401440 KB Execution killed with signal 11
8 Runtime error 237 ms 401744 KB Execution killed with signal 11
9 Runtime error 241 ms 401744 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 881 ms 404168 KB Execution killed with signal 11
2 Runtime error 899 ms 404896 KB Execution killed with signal 11
3 Runtime error 904 ms 404460 KB Execution killed with signal 11
4 Runtime error 865 ms 403264 KB Execution killed with signal 11
5 Runtime error 747 ms 403032 KB Execution killed with signal 11
6 Runtime error 986 ms 404928 KB Execution killed with signal 11
7 Runtime error 889 ms 405168 KB Execution killed with signal 11
8 Runtime error 944 ms 404908 KB Execution killed with signal 11