oj.uz

Submission #642749

# Submission time Handle Problem Language Result Execution time Memory
642749 2022-09-20T12:39:36 Z SlavicG Traffickers (RMI18_traffickers) C++17
35 / 100
 3500 ms 211260 KB 
#include "bits/stdc++.h"
using namespace std;

#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define pb push_back
#define ll long long

const int N = 3e4 + 10;
vector<int> adj[N];
int depth[N];
int p[N];
void dfs(int u, int par) {
    for(int v: adj[u]) {
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        p[v] = u;
        dfs(v, u);
    }
}

vector<int> path(int a, int b) {
    vector<int> left, right;
    while(depth[b] > depth[a]) {
        right.pb(b);
        b = p[b];
    }
    while(depth[a] > depth[b]) {
        left.pb(a);
        a = p[a];
    }
    while(a != b) {
        left.pb(a);
        right.pb(b);
        a = p[a];
        b = p[b];
    }
    left.pb(a);
    reverse(all(right));
    for(auto x: right) left.pb(x);
    return left;
}

ll cnt[N][21][21];
ll pref[N][21][21];

ll calc(vector<int> nodes, ll t) {
    if(t < 0) return 0;
    ll ans = 0;
    for(int d = 1; d <= 21; ++d) {
        for(auto u: nodes) {
            ll sum = pref[u][d][d - 1];
            ans += (t / d) * sum;
            ans += pref[u][d][t % d];
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n; cin >> n;
    for(int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(0, -1);
    int K; cin >> K;
    while(K--) {
        int u, v; cin >> u >> v; --u, --v;
        vector<int> nodes = path(u, v);
        int x = nodes[0];

        for(int i = 0; i < sz(nodes); ++i) {
            cnt[nodes[i]][sz(nodes)][i]++;
        }
        for(int i = 0; i < sz(nodes); ++i) {
            pref[nodes[i]][sz(nodes)][0] = cnt[nodes[i]][sz(nodes)][0];
            for(int j = 1; j < 21; ++j) {
                pref[nodes[i]][sz(nodes)][j] = cnt[nodes[i]][sz(nodes)][j] + pref[nodes[i]][sz(nodes)][j - 1];
            }
        }
    }
    int q; cin >> q;
    while(q--) {
        int type; cin >> type;
        if(type <= 2) {
            int u, v; cin >> u >> v; --u, --v;
            vector<int> nodes = path(u, v);
            int x = nodes[0];
            for(int i = 0; i < sz(nodes); ++i) {
                cnt[nodes[i]][sz(nodes)][i] += (type == 1 ? 1 : -1);
            }

            for(int i = 0; i < sz(nodes); ++i) {
                pref[nodes[i]][sz(nodes)][0] = cnt[nodes[i]][sz(nodes)][0];
                for(int j = 1; j < 21; ++j) {
                    pref[nodes[i]][sz(nodes)][j] = cnt[nodes[i]][sz(nodes)][j] + pref[nodes[i]][sz(nodes)][j - 1];
                }
            }
            continue;
        }
        int u, v, t1, t2; cin >> u >> v >> t1 >> t2; --u, --v;
        vector<int> nodes = path(u, v);
        cout << calc(nodes, t2) - calc(nodes, t1 - 1) << "\n";
    }
}

Compilation message

traffickers.cpp: In function 'int main()':
traffickers.cpp:72:13: warning: unused variable 'x' [-Wunused-variable]
   72 |         int x = nodes[0];
      |             ^
traffickers.cpp:90:17: warning: unused variable 'x' [-Wunused-variable]
   90 |             int x = nodes[0];
      |                 ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 37 ms 8036 KB Output is correct
3 Correct 13 ms 7252 KB Output is correct

Subtask #2
15.0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3592 ms 65728 KB Time limit exceeded
2 Correct 1356 ms 57440 KB Output is correct
3 Execution timed out 3605 ms 66636 KB Time limit exceeded
4 Execution timed out 3586 ms 64752 KB Time limit exceeded
5 Correct 1900 ms 62452 KB Output is correct
6 Correct 2397 ms 63492 KB Output is correct
7 Execution timed out 3603 ms 63320 KB Time limit exceeded
8 Execution timed out 3580 ms 70204 KB Time limit exceeded
9 Execution timed out 3552 ms 70956 KB Time limit exceeded

Subtask #3
5.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3573 ms 208668 KB Time limit exceeded
2 Execution timed out 3600 ms 210332 KB Time limit exceeded
3 Execution timed out 3576 ms 210420 KB Time limit exceeded
4 Execution timed out 3558 ms 202072 KB Time limit exceeded
5 Correct 1071 ms 200468 KB Output is correct
6 Execution timed out 3598 ms 210480 KB Time limit exceeded
7 Execution timed out 3596 ms 211260 KB Time limit exceeded
8 Execution timed out 3583 ms 210940 KB Time limit exceeded