oj.uz

Submission #681581

# Submission time Handle Problem Language Result Execution time Memory
681581 2023-01-13T11:59:12 Z puppy Regions (IOI09_regions) C++17
70 / 100
 4234 ms 131072 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][250];
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]] > 2 * 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] > 2 * 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] <= 2 * 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 3 ms 6224 KB Output is correct
3 Correct 4 ms 6224 KB Output is correct
4 Correct 7 ms 6224 KB Output is correct
5 Correct 11 ms 6224 KB Output is correct
6 Correct 19 ms 6352 KB Output is correct
7 Correct 32 ms 6352 KB Output is correct
8 Correct 32 ms 6352 KB Output is correct
9 Correct 54 ms 6864 KB Output is correct
10 Correct 99 ms 6936 KB Output is correct
11 Correct 135 ms 7248 KB Output is correct
12 Correct 118 ms 7708 KB Output is correct
13 Correct 206 ms 7456 KB Output is correct
14 Correct 324 ms 8144 KB Output is correct
15 Correct 320 ms 10656 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1979 ms 84872 KB Output is correct
2 Correct 2363 ms 88628 KB Output is correct
3 Correct 2614 ms 101412 KB Output is correct
4 Correct 250 ms 8144 KB Output is correct
5 Correct 379 ms 9860 KB Output is correct
6 Correct 662 ms 60528 KB Output is correct
7 Correct 1874 ms 10856 KB Output is correct
8 Correct 1176 ms 16068 KB Output is correct
9 Correct 2321 ms 17048 KB Output is correct
10 Correct 4234 ms 22060 KB Output is correct
11 Correct 4205 ms 17328 KB Output is correct
12 Runtime error 196 ms 131072 KB Execution killed with signal 9
13 Runtime error 181 ms 131072 KB Execution killed with signal 9
14 Runtime error 209 ms 131072 KB Execution killed with signal 9
15 Runtime error 181 ms 131072 KB Execution killed with signal 9
16 Runtime error 249 ms 131072 KB Execution killed with signal 9
17 Runtime error 186 ms 131072 KB Execution killed with signal 9