oj.uz

Submission #627342

# Submission time Handle Problem Language Result Execution time Memory
627342 2022-08-12T13:09:30 Z clams Regions (IOI09_regions) C++17
30 / 100
 1266 ms 49828 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int R = 25e3 + 5;
const int Q = 2e5 + 5;
const int R1 = 505;
const int Q1 = 4000;

int n, r, q;
int home[N], par[N];
vector<int> adj[N];
vector<int> reg[R];

namespace sub1 {
    map<int, int> mp[N];
    int pre[R1][R1];

    void dfs(int u, int p) {
        for (int v : adj[u]) {
            if (v == p) continue;

            dfs(v, u);

            if (mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
            for (auto i : mp[v]) mp[u][i.first] += i.second;
        }
        for (auto i : mp[u]) {
            pre[home[u]][i.first] += i.second;
        }
        mp[u][home[u]]++;
    }

    void solve() {
        dfs(1, 0);

        while (q--) {
            int r1, r2;
            cin >> r1 >> r2;

            cout << pre[r1][r2] << endl;
        }
    }
}

namespace sub2 {

int tin[N], tout[N], timer = 0;

    void dfs(int u, int p) {
        tin[u] = ++timer;
        for (int v : adj[u]) {
            if (v == p) continue;
            dfs(v, u);
        }
        tout[u] = timer;
    }

    bool ischild(int i, int j) {
        return tin[i] <= tin[j] && tout[j] <= tout[i];
    }

    void solve() {
        dfs(1, 0);

        while (q--) {
            int r1, r2;
            cin >> r1 >> r2;

            int ans = 0;
            for (int i : reg[r1]) {
                for (int j : reg[r2]) {
                    ans += (i != j && ischild(i, j));
                }
            }

            cout << ans << endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> r >> q;

    cin >> home[1];
    reg[home[1]].push_back(1);
    for (int i = 2; i <= n; i++) {
        cin >> par[i] >> home[i];
        adj[par[i]].push_back(i);
        adj[i].push_back(par[i]);
        reg[home[i]].push_back(i);
    }

    if (r < R1) {
        sub1::solve();
    } else if (q < Q1) {
        sub2::solve();
    } else {
        assert(false);
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14892 KB Output is correct
2 Correct 10 ms 14928 KB Output is correct
3 Correct 9 ms 15056 KB Output is correct
4 Correct 15 ms 15056 KB Output is correct
5 Correct 13 ms 15056 KB Output is correct
6 Correct 38 ms 15568 KB Output is correct
7 Correct 29 ms 15440 KB Output is correct
8 Correct 43 ms 15568 KB Output is correct
9 Correct 74 ms 16488 KB Output is correct
10 Correct 84 ms 17104 KB Output is correct
11 Correct 104 ms 17228 KB Output is correct
12 Correct 174 ms 17716 KB Output is correct
13 Correct 128 ms 19540 KB Output is correct
14 Correct 146 ms 19252 KB Output is correct
15 Correct 200 ms 22224 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 22060 KB Output is correct
2 Correct 837 ms 24996 KB Output is correct
3 Correct 1266 ms 24620 KB Output is correct
4 Runtime error 33 ms 33196 KB Execution killed with signal 6
5 Runtime error 33 ms 33704 KB Execution killed with signal 6
6 Runtime error 40 ms 35088 KB Execution killed with signal 6
7 Runtime error 44 ms 36924 KB Execution killed with signal 6
8 Runtime error 66 ms 39624 KB Execution killed with signal 6
9 Runtime error 71 ms 44724 KB Execution killed with signal 6
10 Runtime error 76 ms 46668 KB Execution killed with signal 6
11 Runtime error 86 ms 49828 KB Execution killed with signal 6
12 Runtime error 78 ms 47704 KB Execution killed with signal 6
13 Runtime error 82 ms 47824 KB Execution killed with signal 6
14 Runtime error 82 ms 48928 KB Execution killed with signal 6
15 Runtime error 81 ms 49300 KB Execution killed with signal 6
16 Runtime error 79 ms 48992 KB Execution killed with signal 6
17 Runtime error 89 ms 48996 KB Execution killed with signal 6