oj.uz

답안 #731661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731661 2023-04-27T18:10:28 Z Desh03 Regions (IOI09_regions) C++17
30 / 100
 4258 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> r, g;
vector<int> euler, in, out, fr, c;
vector<vector<pair<int, int>>> q;
int t;
const int block = 447;

void dfs(int u) {
    in[u] = t++;
    euler.push_back(u);
    for (int v : g[u])
        dfs(v);
    out[u] = t - 1;
}

void add(int x) {
    fr[c[euler[x]]]++;
}

void remove(int x) {
    fr[c[euler[x]]]--;
}

int main() {
    int n, rr, qq;
    cin >> n >> rr >> qq;
    g.resize(n), r.resize(rr), in.resize(n), out.resize(n), fr.resize(rr), c.resize(n), q.resize(qq);
    map<pair<int, int>, int> ans;
    int x, h;
    cin >> h;
    h--;
    r[h].push_back(0);
    c[0] = h;
    for (int i = 1; i < n; i++) {
        cin >> x >> h;
        x--, h--;
        r[h].push_back(i);
        g[x].push_back(i);
        c[i] = h;
    }
    dfs(0);
    for (int i = 0; i < rr; i++) {
        sort(r[i].begin(), r[i].end(), [](const int &a, const int &b) {
             int a1 = in[a] / block, b1 = in[b] / block;
             return a1 == b1 ? out[a] < out[b] : a1 < b1;
        });
    }
    for (int i = 0; i < rr; i++) {
        int lb, rb;
        if (r[i].size()) lb = in[r[i][0]] + 1, rb = lb - 1;
        for (int u : r[i]) {
            int l_ = in[u] + 1, r_ = out[u];
            while (lb > l_) add(--lb);
            while (rb < r_) add(++rb);
            while (lb < l_) remove(lb++);
            while (rb > r_) remove(rb--);
            for (int j = 0; j < rr; j++)
                if (fr[j]) ans[{i, j}] += fr[j];
        }
        if (r[i].size()) for (int j = 0; j < rr; j++) fr[j] = 0;
    }
    while (qq--) {
        int a, b;
        cin >> a >> b;
        cout << ans[{--a, --b}] << endl;
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 6 ms 336 KB Output is correct
5 Correct 9 ms 464 KB Output is correct
6 Correct 45 ms 3680 KB Output is correct
7 Correct 37 ms 1456 KB Output is correct
8 Correct 32 ms 2684 KB Output is correct
9 Correct 239 ms 6700 KB Output is correct
10 Correct 166 ms 9168 KB Output is correct
11 Correct 242 ms 6368 KB Output is correct
12 Correct 802 ms 15160 KB Output is correct
13 Correct 260 ms 7168 KB Output is correct
14 Correct 295 ms 5396 KB Output is correct
15 Correct 1366 ms 9240 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2338 ms 11012 KB Output is correct
2 Correct 1689 ms 10780 KB Output is correct
3 Correct 4258 ms 16240 KB Output is correct
4 Runtime error 1140 ms 131072 KB Execution killed with signal 9
5 Runtime error 2128 ms 131072 KB Execution killed with signal 9
6 Runtime error 1273 ms 131072 KB Execution killed with signal 9
7 Runtime error 1026 ms 131072 KB Execution killed with signal 9
8 Runtime error 1939 ms 131072 KB Execution killed with signal 9
9 Runtime error 1604 ms 131072 KB Execution killed with signal 9
10 Runtime error 912 ms 131072 KB Execution killed with signal 9
11 Runtime error 2666 ms 131072 KB Execution killed with signal 9
12 Runtime error 3275 ms 131072 KB Execution killed with signal 9
13 Runtime error 1718 ms 131072 KB Execution killed with signal 9
14 Runtime error 3904 ms 131072 KB Execution killed with signal 9
15 Runtime error 1351 ms 131072 KB Execution killed with signal 9
16 Runtime error 2146 ms 131072 KB Execution killed with signal 9
17 Runtime error 2717 ms 131072 KB Execution killed with signal 9