oj.uz

Submission #681583

# Submission time Handle Problem Language Result Execution time Memory
681583 2023-01-13T12:02:45 Z puppy Regions (IOI09_regions) C++17
70 / 100
 4547 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]] > 6 * 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] > 6 * 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] <= 6 * 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 4 ms 6224 KB Output is correct
2 Correct 4 ms 6224 KB Output is correct
3 Correct 6 ms 6224 KB Output is correct
4 Correct 6 ms 6224 KB Output is correct
5 Correct 9 ms 6352 KB Output is correct
6 Correct 12 ms 6352 KB Output is correct
7 Correct 16 ms 6332 KB Output is correct
8 Correct 32 ms 6352 KB Output is correct
9 Correct 63 ms 6864 KB Output is correct
10 Correct 81 ms 6864 KB Output is correct
11 Correct 128 ms 7248 KB Output is correct
12 Correct 165 ms 7724 KB Output is correct
13 Correct 174 ms 7508 KB Output is correct
14 Correct 298 ms 8144 KB Output is correct
15 Correct 252 ms 10720 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1994 ms 61304 KB Output is correct
2 Correct 2789 ms 63572 KB Output is correct
3 Correct 2766 ms 73248 KB Output is correct
4 Correct 300 ms 8192 KB Output is correct
5 Correct 414 ms 9780 KB Output is correct
6 Correct 1388 ms 9540 KB Output is correct
7 Correct 1653 ms 10796 KB Output is correct
8 Correct 1083 ms 16000 KB Output is correct
9 Correct 2407 ms 16936 KB Output is correct
10 Correct 4547 ms 22108 KB Output is correct
11 Correct 4397 ms 17244 KB Output is correct
12 Runtime error 197 ms 131072 KB Execution killed with signal 9
13 Runtime error 231 ms 131072 KB Execution killed with signal 9
14 Runtime error 211 ms 131072 KB Execution killed with signal 9
15 Runtime error 190 ms 131072 KB Execution killed with signal 9
16 Runtime error 230 ms 131072 KB Execution killed with signal 9
17 Runtime error 176 ms 131072 KB Execution killed with signal 9