oj.uz

답안 #627298

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
627298 2022-08-12T12:14:58 Z clams Regions (IOI09_regions) C++17
30 / 100
 1126 ms 93072 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int R = 25e3 + 5;
const int Q = 2e5 + 5;

int n, r, q;
int home[N], par[N];
vector<int> adj[N];

const int R1 = 505;

map<int, int> mp[N];
int pre[R1][R1];

void dfs(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;

        dfs(v, u);

        if (mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
        for (auto i : mp[v]) mp[u][i.first] += i.second;
    }
    for (auto i : mp[u]) {
        pre[home[u]][i.first] += i.second;
    }
    mp[u][home[u]]++;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> r >> q;

    cin >> home[1];
    for (int i = 2; i <= n; i++) {
        cin >> par[i] >> home[i];
        adj[par[i]].push_back(i);
        adj[i].push_back(par[i]);
    }

    dfs(1, 0);

    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;

        cout << pre[r1][r2] << endl;
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14416 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 9 ms 14416 KB Output is correct
4 Correct 13 ms 14416 KB Output is correct
5 Correct 15 ms 14544 KB Output is correct
6 Correct 36 ms 15052 KB Output is correct
7 Correct 23 ms 14800 KB Output is correct
8 Correct 20 ms 15056 KB Output is correct
9 Correct 65 ms 15852 KB Output is correct
10 Correct 45 ms 16464 KB Output is correct
11 Correct 98 ms 16496 KB Output is correct
12 Correct 158 ms 17036 KB Output is correct
13 Correct 139 ms 18764 KB Output is correct
14 Correct 158 ms 18408 KB Output is correct
15 Correct 237 ms 21472 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 664 ms 20988 KB Output is correct
2 Correct 756 ms 23924 KB Output is correct
3 Correct 1126 ms 23396 KB Output is correct
4 Runtime error 28 ms 32076 KB Execution killed with signal 11
5 Runtime error 36 ms 32368 KB Execution killed with signal 11
6 Runtime error 35 ms 34120 KB Execution killed with signal 11
7 Runtime error 47 ms 34672 KB Execution killed with signal 11
8 Runtime error 46 ms 39112 KB Execution killed with signal 11
9 Runtime error 63 ms 41096 KB Execution killed with signal 11
10 Runtime error 66 ms 42984 KB Execution killed with signal 11
11 Runtime error 75 ms 45448 KB Execution killed with signal 11
12 Runtime error 70 ms 44116 KB Execution killed with signal 11
13 Runtime error 67 ms 44216 KB Execution killed with signal 11
14 Runtime error 70 ms 44872 KB Execution killed with signal 11
15 Runtime error 89 ms 49080 KB Execution killed with signal 11
16 Runtime error 107 ms 93072 KB Execution killed with signal 11
17 Runtime error 71 ms 45004 KB Execution killed with signal 11