oj.uz

Submission #627339

# Submission time Handle Problem Language Result Execution time Memory
627339 2022-08-12T13:05:24 Z clams Regions (IOI09_regions) C++17
55 / 100
 8000 ms 34632 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;

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 {
        sub2::solve();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14980 KB Output is correct
2 Correct 10 ms 14912 KB Output is correct
3 Correct 10 ms 15056 KB Output is correct
4 Correct 13 ms 15056 KB Output is correct
5 Correct 17 ms 15056 KB Output is correct
6 Correct 29 ms 15656 KB Output is correct
7 Correct 41 ms 15440 KB Output is correct
8 Correct 22 ms 15568 KB Output is correct
9 Correct 70 ms 16464 KB Output is correct
10 Correct 102 ms 17240 KB Output is correct
11 Correct 66 ms 17208 KB Output is correct
12 Correct 142 ms 17756 KB Output is correct
13 Correct 164 ms 19540 KB Output is correct
14 Correct 144 ms 19160 KB Output is correct
15 Correct 283 ms 22260 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 22068 KB Output is correct
2 Correct 872 ms 24964 KB Output is correct
3 Correct 1139 ms 24540 KB Output is correct
4 Correct 210 ms 16680 KB Output is correct
5 Correct 438 ms 18124 KB Output is correct
6 Execution timed out 8093 ms 18044 KB Time limit exceeded
7 Correct 6264 ms 19036 KB Output is correct
8 Correct 3272 ms 23600 KB Output is correct
9 Correct 5724 ms 24124 KB Output is correct
10 Execution timed out 8086 ms 28608 KB Time limit exceeded
11 Execution timed out 8058 ms 26372 KB Time limit exceeded
12 Execution timed out 8095 ms 25288 KB Time limit exceeded
13 Execution timed out 8054 ms 25980 KB Time limit exceeded
14 Execution timed out 8076 ms 26060 KB Time limit exceeded
15 Execution timed out 8053 ms 29108 KB Time limit exceeded
16 Execution timed out 8042 ms 34632 KB Time limit exceeded
17 Execution timed out 8032 ms 33524 KB Time limit exceeded