oj.uz

Submission #753624

# Submission time Handle Problem Language Result Execution time Memory
753624 2023-06-05T14:56:10 Z CpDark Regions (IOI09_regions) C++17
30 / 100
 2277 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<double, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef vector<vb> vvb;

vvi graph;
vi home;
vector<map<int, int>> mp;
map<int,map<int, int>> ans;

inline void merge(map<int, int> &a, map<int, int>&b) {
    for (auto curr : b) {
        a[curr.first] += curr.second;
    }
}

inline void update(int v) {
    for (auto curr : mp[v]) {
        ans[home[v]][curr.first] += curr.second;
    }
}

void dfs(int v, int p) {
    mp[v][home[v]]++;
    int index = v;
    int size = 1;
    for (int i = 0;i < graph[v].size();i++) {
        int u = graph[v][i];
        if (u != p) {
            dfs(u, v);
            if (mp[u].size() > size) {
                size = mp[u].size();
                index = u;
            }
        }
    }
    
    if (index != v) {
        swap(mp[v], mp[index]);
        merge(mp[v], mp[index]);
        mp[index].clear();
    }
    for (int i = 0;i < graph[v].size();i++) {
        int u = graph[v][i];
        if (u != p && u != index) {
            merge(mp[v], mp[u]);
            mp[u].clear();
        }  
    }
    
    update(v);
}

inline int query(int r1, int r2) {
    if (ans.find(r1) == ans.end() || ans[r1].find(r2) == ans[r1].end())return 0;
    return ans[r1][r2];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r, q;
    cin >> n >> r >> q;
    home.resize(n + 1);
    graph.resize(n + 1);
    mp.resize(n + 1);
    cin >> home[1];

    int p;
    for (int i = 0;i < n - 1;i++) {
        cin >> p >> home[i + 2];
        graph[i + 2].push_back(p);
        graph[p].push_back(i + 2);
    }

    dfs(1, 1);
    int r1, r2;
    for (int i = 0;i < q;i++) {
        cin >> r1 >> r2;
        int curr = query(r1, r2);
        cout << curr << endl;
    }

    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0;i < graph[v].size();i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
regions.cpp:40:30: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |             if (mp[u].size() > size) {
      |                 ~~~~~~~~~~~~~^~~~~~
regions.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0;i < graph[v].size();i++) {
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 10 ms 464 KB Output is correct
6 Correct 28 ms 2860 KB Output is correct
7 Correct 29 ms 1104 KB Output is correct
8 Correct 28 ms 2000 KB Output is correct
9 Correct 143 ms 6124 KB Output is correct
10 Correct 121 ms 7184 KB Output is correct
11 Correct 107 ms 5576 KB Output is correct
12 Correct 518 ms 12984 KB Output is correct
13 Correct 195 ms 6372 KB Output is correct
14 Correct 202 ms 5756 KB Output is correct
15 Correct 883 ms 15336 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 13480 KB Output is correct
2 Correct 936 ms 11816 KB Output is correct
3 Correct 2277 ms 20188 KB Output is correct
4 Runtime error 801 ms 131072 KB Execution killed with signal 9
5 Runtime error 1178 ms 131072 KB Execution killed with signal 9
6 Runtime error 881 ms 131072 KB Execution killed with signal 9
7 Runtime error 552 ms 131072 KB Execution killed with signal 9
8 Runtime error 924 ms 131072 KB Execution killed with signal 9
9 Runtime error 614 ms 131072 KB Execution killed with signal 9
10 Runtime error 982 ms 131072 KB Execution killed with signal 9
11 Runtime error 723 ms 131072 KB Execution killed with signal 9
12 Runtime error 994 ms 131072 KB Execution killed with signal 9
13 Runtime error 831 ms 131072 KB Execution killed with signal 9
14 Runtime error 934 ms 131072 KB Execution killed with signal 9
15 Runtime error 672 ms 131072 KB Execution killed with signal 9
16 Runtime error 540 ms 131072 KB Execution killed with signal 9
17 Runtime error 666 ms 131072 KB Execution killed with signal 9