oj.uz

Submission #764231

# Submission time Handle Problem Language Result Execution time Memory
764231 2023-06-23T09:05:06 Z Alma Regions (IOI09_regions) C++17
0 / 100
 1694 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> region;
vector<bool> vis, calc;
vector<vector<int>> adj, dp, distrib;

void dfs(int u, int r) {
    vis[u] = true;

    if (region[u] != r) {
        dp[r][region[u]]++;
    } 
    for (int v: adj[u]) {
        if (!vis[v]) dfs(v, r);
    }
}

void dfs2(int u, int r, int cnt) {
    vis[u] = true;

    if (region[u] == r) {
        dp[r][region[u]] += cnt;
        cnt++;
    }
    for (int v: adj[u]) {
        if (!vis[v]) dfs2(v, r, cnt);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, r, q, h, s, r1, r2;
    cin >> n >> r >> q;

    region = vector<int>(n);
    adj = vector<vector<int>>(n);
    distrib = vector<vector<int>>(n);

    cin >> h;
    h--;
    region[0] = h;
    distrib[h].push_back(0);

    for (int i = 1; i < n; i++) {
        cin >> s >> h;
        h--; s--;
        region[i] = h;
        distrib[h].push_back(i);
        adj[s].push_back(i);
    }

    calc = vector<bool> (r, false);
    dp = vector<vector<int>> (r, vector<int>(r, 0));

    while (q--) {
        cin >> r1 >> r2;
        r1--; r2--;
        
        if (not calc[r1]) {
            vis = vector<bool>(n, false);
            for (int i: distrib[r1]) {
                if (!vis[i]) dfs(i, r1);
            }
            vis = vector<bool>(n, false);
            dfs2(0, r1, 0);
            calc[r1] = true;
        }

        cout << dp[r1][r2] << endl << flush;
    }

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Incorrect 0 ms 208 KB Output isn't correct
3 Incorrect 2 ms 208 KB Output isn't correct
4 Incorrect 3 ms 336 KB Output isn't correct
5 Incorrect 6 ms 336 KB Output isn't correct
6 Incorrect 13 ms 592 KB Output isn't correct
7 Incorrect 22 ms 464 KB Output isn't correct
8 Incorrect 32 ms 592 KB Output isn't correct
9 Incorrect 76 ms 1360 KB Output isn't correct
10 Incorrect 141 ms 1876 KB Output isn't correct
11 Incorrect 182 ms 1944 KB Output isn't correct
12 Incorrect 331 ms 3116 KB Output isn't correct
13 Incorrect 247 ms 2568 KB Output isn't correct
14 Incorrect 293 ms 3032 KB Output isn't correct
15 Incorrect 373 ms 5996 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 959 ms 7636 KB Output isn't correct
2 Incorrect 1350 ms 6692 KB Output isn't correct
3 Incorrect 1582 ms 10088 KB Output isn't correct
4 Incorrect 1416 ms 65708 KB Output isn't correct
5 Incorrect 1694 ms 102864 KB Output isn't correct
6 Runtime error 59 ms 131072 KB Execution killed with signal 9
7 Runtime error 57 ms 131072 KB Execution killed with signal 9
8 Runtime error 64 ms 131072 KB Execution killed with signal 9
9 Runtime error 101 ms 131072 KB Execution killed with signal 9
10 Runtime error 72 ms 131072 KB Execution killed with signal 9
11 Runtime error 87 ms 131072 KB Execution killed with signal 9
12 Runtime error 83 ms 131072 KB Execution killed with signal 9
13 Runtime error 77 ms 131072 KB Execution killed with signal 9
14 Runtime error 96 ms 131072 KB Execution killed with signal 9
15 Runtime error 95 ms 131072 KB Execution killed with signal 9
16 Runtime error 87 ms 131072 KB Execution killed with signal 9
17 Runtime error 91 ms 131072 KB Execution killed with signal 9