oj.uz

답안 #731491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731491 2023-04-27T13:28:43 Z Desh03 Regions (IOI09_regions) C++17
35 / 100
 8000 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;

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

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);
    vector<vector<int>> ans(rr, vector<int> (rr));
    int x, h;
    cin >> h;
    h--;
    r[h].push_back(0);
    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++) {
        for (int u : r[i]) {
            for (int j = in[u] + 1; j <= out[u]; j++) fr[c[euler[j]]]++;
        }
        for (int j = 0; j < rr; j++) ans[i][j] = fr[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 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 24 ms 592 KB Output is correct
7 Correct 26 ms 464 KB Output is correct
8 Correct 32 ms 720 KB Output is correct
9 Correct 112 ms 1420 KB Output is correct
10 Correct 72 ms 2004 KB Output is correct
11 Correct 112 ms 2052 KB Output is correct
12 Correct 305 ms 3396 KB Output is correct
13 Correct 98 ms 2724 KB Output is correct
14 Correct 173 ms 3144 KB Output is correct
15 Correct 3039 ms 6060 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2770 ms 8924 KB Output is correct
2 Correct 1383 ms 8156 KB Output is correct
3 Execution timed out 8032 ms 12444 KB Time limit exceeded
4 Correct 446 ms 66272 KB Output is correct
5 Correct 2089 ms 103484 KB Output is correct
6 Runtime error 63 ms 131072 KB Execution killed with signal 9
7 Runtime error 67 ms 131072 KB Execution killed with signal 9
8 Runtime error 70 ms 131072 KB Execution killed with signal 9
9 Runtime error 60 ms 131072 KB Execution killed with signal 9
10 Runtime error 59 ms 131072 KB Execution killed with signal 9
11 Runtime error 64 ms 131072 KB Execution killed with signal 9
12 Runtime error 60 ms 131072 KB Execution killed with signal 9
13 Runtime error 66 ms 131072 KB Execution killed with signal 9
14 Runtime error 56 ms 131072 KB Execution killed with signal 9
15 Runtime error 62 ms 131072 KB Execution killed with signal 9
16 Runtime error 66 ms 131072 KB Execution killed with signal 9
17 Runtime error 54 ms 131072 KB Execution killed with signal 9