oj.uz

Submission #1090197

# Submission time Handle Problem Language Result Execution time Memory
1090197 2024-09-18T00:31:44 Z efishel Synchronization (JOI13_synchronization) C++17
10 / 100
 8000 ms 16008 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1E5+16;
vii adj[MAXN];
bool isOn[MAXN];
ii edg[MAXN];
ll ans[MAXN];
ii last[MAXN];

void dfs (ll u, ll par, ll add) {
    ans[u] += add;
    for (auto [v, id] : adj[u]) {
        if (v == par || !isOn[id]) continue;
        dfs(v, u, add);
    }
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, Q, qa;
    cin >> n >> Q >> qa;
    for (ll id = 1; id < n; id++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].push_back({ v, id });
        adj[v].push_back({ u, id });
        edg[id] = { u, v };
    }
    fill(isOn, isOn+n, false);
    fill(ans, ans+n, 1);
    fill(last, last+n, ii{ 0, 0 });
    while (Q--) {
        ll id;
        cin >> id;
        auto [u, v] = edg[id];
        if (isOn[id] ^= 1) {
            ll sumU = ans[v] - last[id].second; // how much v has grown
            ll sumV = ans[u] - last[id].first; // how much u has grown
            dfs(u, v, sumU);
            dfs(v, u, sumV);
        } else {
            last[id] = ii{ ans[u], ans[v] };
        }
    }
    while (qa--) {
        ll u;
        cin >> u;
        u--;
        cout << ans[u] << '\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 7 ms 3824 KB Output is correct
8 Correct 7 ms 3932 KB Output is correct
9 Correct 8 ms 3924 KB Output is correct
10 Correct 99 ms 14116 KB Output is correct
11 Correct 98 ms 14244 KB Output is correct
12 Correct 45 ms 13656 KB Output is correct
13 Execution timed out 8038 ms 12480 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8051 ms 15736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2828 KB Output is correct
7 Correct 5 ms 3932 KB Output is correct
8 Correct 54 ms 14444 KB Output is correct
9 Correct 56 ms 14476 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 14416 KB Output is correct
2 Execution timed out 8061 ms 16008 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2832 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 10 ms 4000 KB Output is correct
7 Correct 116 ms 15068 KB Output is correct
8 Correct 56 ms 14416 KB Output is correct
9 Execution timed out 8057 ms 12492 KB Time limit exceeded
10 Halted 0 ms 0 KB -