Submission #642749

#	Time	Username	Problem	Language	Result	Execution time	Memory
642749		SlavicG	Traffickers (RMI18_traffickers)	C++17	35 / 100	3605 ms	211260 KiB

traffickers

#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 (stderr)

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 / 15
• Subtask 2: 15 / 45
• Subtask 3: 5 / 40