oj.uz

답안 #731694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731694 2023-04-27T19:49:18 Z Desh03 Regions (IOI09_regions) C++17
19 / 100
 8000 ms 25000 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> r[25000], g[200000], euler;
int in[200000], out[200000];
short int c[200000];
int t;

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

int main() {
    int n, rr, qq;
    cin >> n >> rr >> qq;
    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);
    while (qq--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        int ans = 0;
        for (int u : r[a]) {
           for (int i = in[u] + 1; i <= out[u]; i++) {
                ans += euler[i] == b;
           }
        }
        cout << ans << '\n';
    }
}

Subtask #1
14.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 6 ms 5584 KB Output is correct
4 Correct 5 ms 5584 KB Output is correct
5 Correct 10 ms 5584 KB Output is correct
6 Correct 23 ms 5584 KB Output is correct
7 Correct 26 ms 5584 KB Output is correct
8 Correct 38 ms 5712 KB Output is correct
9 Correct 193 ms 6096 KB Output is correct
10 Correct 104 ms 6128 KB Output is correct
11 Correct 252 ms 6372 KB Output is correct
12 Correct 845 ms 6944 KB Output is correct
13 Correct 164 ms 6608 KB Output is correct
14 Correct 457 ms 7160 KB Output is correct
15 Execution timed out 8084 ms 9544 KB Time limit exceeded

Subtask #2
5.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8069 ms 10132 KB Time limit exceeded
2 Execution timed out 8045 ms 9028 KB Time limit exceeded
3 Execution timed out 8004 ms 11976 KB Time limit exceeded
4 Correct 1383 ms 7372 KB Output is correct
5 Execution timed out 8023 ms 8904 KB Time limit exceeded
6 Execution timed out 8077 ms 8268 KB Time limit exceeded
7 Execution timed out 8080 ms 9412 KB Time limit exceeded
8 Execution timed out 8038 ms 14084 KB Time limit exceeded
9 Execution timed out 8009 ms 14604 KB Time limit exceeded
10 Execution timed out 8052 ms 18876 KB Time limit exceeded
11 Execution timed out 8045 ms 14008 KB Time limit exceeded
12 Execution timed out 8071 ms 15700 KB Time limit exceeded
13 Execution timed out 8083 ms 15816 KB Time limit exceeded
14 Execution timed out 8079 ms 15568 KB Time limit exceeded
15 Execution timed out 8070 ms 19676 KB Time limit exceeded
16 Execution timed out 8089 ms 25000 KB Time limit exceeded
17 Execution timed out 8048 ms 23860 KB Time limit exceeded