oj.uz

답안 #642748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
642748 2022-09-20T12:39:02 Z SlavicG Traffickers (RMI18_traffickers) C++17
20 / 100
 3500 ms 211116 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;
            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];

        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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 198 ms 8148 KB Output is correct
3 Correct 16 ms 7204 KB Output is correct

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3599 ms 65036 KB Time limit exceeded
2 Execution timed out 3567 ms 57456 KB Time limit exceeded
3 Execution timed out 3583 ms 66600 KB Time limit exceeded
4 Execution timed out 3598 ms 63876 KB Time limit exceeded
5 Execution timed out 3591 ms 61432 KB Time limit exceeded
6 Execution timed out 3584 ms 62592 KB Time limit exceeded
7 Execution timed out 3556 ms 62824 KB Time limit exceeded
8 Execution timed out 3557 ms 69904 KB Time limit exceeded
9 Execution timed out 3554 ms 70940 KB Time limit exceeded

Subtask #3
5.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3584 ms 208600 KB Time limit exceeded
2 Execution timed out 3559 ms 210296 KB Time limit exceeded
3 Execution timed out 3580 ms 210268 KB Time limit exceeded
4 Execution timed out 3549 ms 201688 KB Time limit exceeded
5 Correct 3139 ms 200432 KB Output is correct
6 Execution timed out 3578 ms 210536 KB Time limit exceeded
7 Execution timed out 3607 ms 211116 KB Time limit exceeded
8 Execution timed out 3614 ms 210780 KB Time limit exceeded