oj.uz

Submission #764190

# Submission time Handle Problem Language Result Execution time Memory
764190 2023-06-23T08:28:34 Z Alma Regions (IOI09_regions) C++17
0 / 100
 1288 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);
    }
}

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);
    }

    // for (int i: region)
    //     cout << i << ' ';
    // cout << endl;

    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);
            }
            calc[r1] = true;
        }

        // if (not calc[r2]) {
        //     vis = vector<bool>(n, false);
        //     for (int i: distrib[r2]) {
        //         if (!vis[i]) dfs(i, r2);
        //     }
        // }

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

        // for (int i = 0; i < r; i++) {
        //     cout << dp[r1][i] << ' ';
        // }
        // cout << endl;
    }

    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 1 ms 208 KB Output isn't correct
3 Incorrect 2 ms 208 KB Output isn't correct
4 Incorrect 4 ms 208 KB Output isn't correct
5 Incorrect 6 ms 336 KB Output isn't correct
6 Incorrect 16 ms 592 KB Output isn't correct
7 Incorrect 14 ms 464 KB Output isn't correct
8 Incorrect 33 ms 672 KB Output isn't correct
9 Incorrect 53 ms 1360 KB Output isn't correct
10 Incorrect 73 ms 1872 KB Output isn't correct
11 Incorrect 99 ms 1932 KB Output isn't correct
12 Incorrect 236 ms 3112 KB Output isn't correct
13 Incorrect 124 ms 2568 KB Output isn't correct
14 Incorrect 195 ms 3036 KB Output isn't correct
15 Incorrect 187 ms 5964 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 902 ms 7636 KB Output isn't correct
2 Incorrect 869 ms 6684 KB Output isn't correct
3 Incorrect 1288 ms 10088 KB Output isn't correct
4 Incorrect 464 ms 65712 KB Output isn't correct
5 Incorrect 893 ms 102856 KB Output isn't correct
6 Runtime error 56 ms 131072 KB Execution killed with signal 9
7 Runtime error 55 ms 131072 KB Execution killed with signal 9
8 Runtime error 74 ms 131072 KB Execution killed with signal 9
9 Runtime error 78 ms 131072 KB Execution killed with signal 9
10 Runtime error 73 ms 131072 KB Execution killed with signal 9
11 Runtime error 100 ms 131072 KB Execution killed with signal 9
12 Runtime error 85 ms 131072 KB Execution killed with signal 9
13 Runtime error 78 ms 131072 KB Execution killed with signal 9
14 Runtime error 107 ms 131072 KB Execution killed with signal 9
15 Runtime error 84 ms 131072 KB Execution killed with signal 9
16 Runtime error 112 ms 131072 KB Execution killed with signal 9
17 Runtime error 95 ms 131072 KB Execution killed with signal 9