oj.uz

Submission #642743

# Submission time Handle Problem Language Result Execution time Memory
642743 2022-09-20T12:36:39 Z SlavicG Traffickers (RMI18_traffickers) C++17
15 / 100
 3500 ms 211152 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 = 0;
            for(int j = 0; j <= d; ++j) sum += cnt[u][d][j];
            ans += (t / d) * sum;
            for(int j = 0; j <= t % d; ++j) ans += cnt[u][d][j];
        }
    }
    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];
        //nodes.erase(nodes.begin());
        //nodes.pb(x);

        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];
            //nodes.erase(nodes.begin());
            //nodes.pb(x);
            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:73:13: warning: unused variable 'x' [-Wunused-variable]
   73 |         int x = nodes[0];
      |             ^
traffickers.cpp:93:17: warning: unused variable 'x' [-Wunused-variable]
   93 |             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 187 ms 8032 KB Output is correct
3 Correct 24 ms 7240 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3599 ms 64976 KB Time limit exceeded
2 Execution timed out 3583 ms 57412 KB Time limit exceeded
3 Execution timed out 3600 ms 66572 KB Time limit exceeded
4 Execution timed out 3600 ms 64112 KB Time limit exceeded
5 Execution timed out 3601 ms 61716 KB Time limit exceeded
6 Execution timed out 3601 ms 62448 KB Time limit exceeded
7 Execution timed out 3568 ms 62924 KB Time limit exceeded
8 Execution timed out 3601 ms 69836 KB Time limit exceeded
9 Execution timed out 3602 ms 70956 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3602 ms 208596 KB Time limit exceeded
2 Execution timed out 3611 ms 210180 KB Time limit exceeded
3 Execution timed out 3611 ms 210240 KB Time limit exceeded
4 Execution timed out 3607 ms 201624 KB Time limit exceeded
5 Incorrect 3222 ms 200560 KB Output isn't correct
6 Execution timed out 3597 ms 210528 KB Time limit exceeded
7 Execution timed out 3598 ms 211152 KB Time limit exceeded
8 Execution timed out 3586 ms 210824 KB Time limit exceeded