oj.uz

Submission #681584

# Submission time Handle Problem Language Result Execution time Memory
681584 2023-01-13T12:05:14 Z puppy Regions (IOI09_regions) C++17
100 / 100
 4436 ms 86964 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;
int N, SQ;
int R, Q;
int cnt[25005];
int cpx[25005];
int region[200005], par[200005];
int s[200005], e[200005];
int dp[200005][75];
vector<int> g[200005];
vector<int> exceed;
vector<int> ett;
void dfs(int v)
{
    s[v] = (int)ett.size() + 1;
    ett.push_back(v);
    for (auto &i:g[v]) dfs(i);
    e[v] = (int)ett.size() - 1;
}
void dfs2(int v, int p)
{
    int loc = -1;
    if (cnt[region[v]] > 8 * SQ) loc = cpx[region[v]];
    for (int i = 0; i < (int)exceed.size(); i++) {
        dp[v][i] = dp[p][i] + (i == loc);
    }
    for (auto &i:g[v]) dfs2(i, v);
}
vector<int> pos[25005];
vector<int> member[25005];
int main()
{
    cin >> N >> R >> Q;
    SQ = sqrt(N);
    fill(cpx, cpx + 25005, -1);
    for (int i = 1; i <= N; i++) {
        if (i >= 2) cin >> par[i], g[par[i]].push_back(i);
        cin >> region[i];
        member[region[i]].push_back(i);
        cnt[region[i]]++;
    }
    dfs(1);
    for (int i = 0; i < N; i++) {
        pos[region[ett[i]]].push_back(i);
    }
    for (int i = 1; i <= R; i++) {
        if (cnt[i] > 8 * SQ) exceed.push_back(i);
    }
    for (int k = 0; k < (int)exceed.size(); k++) cpx[exceed[k]] = k;
    dfs2(1, 0);
    map<pair<int, int>, int> res;
    while (Q--) {
        int r1, r2; cin >> r1 >> r2;
        int ans = 0;
        if (cnt[r1] <= 8 * SQ) {
            for (int &i:member[r1]) {
                //r2 색 중 i의 서브트리 내부에들어오는 것 개수
                int st = lower_bound(pos[r2].begin(), pos[r2].end(), s[i]) - pos[r2].begin();
                int en = upper_bound(pos[r2].begin(), pos[r2].end(), e[i]) - pos[r2].begin();
                --en;
                ans += (en - st + 1);
            }
        }
        else {
            bool flag = false;
            if (cnt[r2] > SQ) {
                int tmp = res[make_pair(r1, r2)];
                if (tmp > 0) ans = tmp - 1, flag = true;
            }
            if (!flag) {
                for (int &i:member[r2]) {
                    ans += dp[par[i]][cpx[r1]];
                }
                if (cnt[r2] > SQ) res[make_pair(r1, r2)] = ans + 1;
            }
        }
        cout << ans << '\n';
        cout.flush();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6224 KB Output is correct
2 Correct 4 ms 6224 KB Output is correct
3 Correct 4 ms 6224 KB Output is correct
4 Correct 11 ms 6224 KB Output is correct
5 Correct 12 ms 6264 KB Output is correct
6 Correct 24 ms 6352 KB Output is correct
7 Correct 36 ms 6352 KB Output is correct
8 Correct 44 ms 6352 KB Output is correct
9 Correct 51 ms 6864 KB Output is correct
10 Correct 95 ms 6916 KB Output is correct
11 Correct 139 ms 7248 KB Output is correct
12 Correct 142 ms 7792 KB Output is correct
13 Correct 217 ms 7500 KB Output is correct
14 Correct 315 ms 8088 KB Output is correct
15 Correct 283 ms 10824 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1860 ms 33516 KB Output is correct
2 Correct 2692 ms 33852 KB Output is correct
3 Correct 3074 ms 39824 KB Output is correct
4 Correct 206 ms 8136 KB Output is correct
5 Correct 358 ms 9804 KB Output is correct
6 Correct 1206 ms 9544 KB Output is correct
7 Correct 1724 ms 10824 KB Output is correct
8 Correct 1202 ms 15996 KB Output is correct
9 Correct 2440 ms 16900 KB Output is correct
10 Correct 3846 ms 22060 KB Output is correct
11 Correct 4436 ms 17236 KB Output is correct
12 Correct 1542 ms 74172 KB Output is correct
13 Correct 2017 ms 74416 KB Output is correct
14 Correct 2698 ms 77352 KB Output is correct
15 Correct 3081 ms 81760 KB Output is correct
16 Correct 2742 ms 86964 KB Output is correct
17 Correct 2805 ms 85820 KB Output is correct