oj.uz

Submission #681582

# Submission time Handle Problem Language Result Execution time Memory
681582 2023-01-13T12:00:49 Z puppy Regions (IOI09_regions) C++17
70 / 100
 4342 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][170];
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]] > 3 * 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] > 3 * 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] <= 3 * 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 5 ms 6224 KB Output is correct
4 Correct 8 ms 6224 KB Output is correct
5 Correct 10 ms 6224 KB Output is correct
6 Correct 23 ms 6352 KB Output is correct
7 Correct 34 ms 6352 KB Output is correct
8 Correct 36 ms 6352 KB Output is correct
9 Correct 50 ms 6864 KB Output is correct
10 Correct 79 ms 6984 KB Output is correct
11 Correct 128 ms 7248 KB Output is correct
12 Correct 113 ms 7704 KB Output is correct
13 Correct 128 ms 7504 KB Output is correct
14 Correct 325 ms 8012 KB Output is correct
15 Correct 287 ms 10708 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2230 ms 61380 KB Output is correct
2 Correct 2373 ms 63644 KB Output is correct
3 Correct 3290 ms 73304 KB Output is correct
4 Correct 261 ms 8132 KB Output is correct
5 Correct 396 ms 9812 KB Output is correct
6 Correct 1353 ms 9552 KB Output is correct
7 Correct 1847 ms 10780 KB Output is correct
8 Correct 1446 ms 15960 KB Output is correct
9 Correct 2508 ms 16956 KB Output is correct
10 Correct 4177 ms 21988 KB Output is correct
11 Correct 4342 ms 17340 KB Output is correct
12 Runtime error 196 ms 131072 KB Execution killed with signal 9
13 Runtime error 184 ms 131072 KB Execution killed with signal 9
14 Runtime error 222 ms 131072 KB Execution killed with signal 9
15 Runtime error 210 ms 131072 KB Execution killed with signal 9
16 Runtime error 184 ms 131072 KB Execution killed with signal 9
17 Runtime error 186 ms 131072 KB Execution killed with signal 9