Submission #753624

#	Time	Username	Problem	Language	Result	Execution time	Memory
753624		CpDark	Regions (IOI09_regions)	C++17	30 / 100	2277 ms	131072 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 15 / 85