Submission #1016236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016236		socpite	Regions (IOI09_regions)	C++14	45 / 100	1945 ms	131072 KiB

regions

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
const int maxr = 25005;
const int blsz = 500;

int n, r, q;

int bigans[blsz][maxr];
int cnt[maxr], bigid[maxr], H[maxn];

int bigcnt = 0, tdfs = 0;

vector<int> g[maxn];
vector<pair<int, int>> euler[maxr];

void dfs(int x){
    tdfs++;
    euler[H[x]].push_back({tdfs, 1});
    cnt[H[x]]++;
    for(auto v: g[x])dfs(v);
    tdfs++;
    euler[H[x]].push_back({tdfs, -1});
}

void dfs_calc(int x, int id, int dep){
    if(H[x] == id)dep++;
    else bigans[bigcnt][H[x]] += dep;
    for(auto v: g[x])dfs_calc(x, id, dep);
}

int main() {
    cin >> n >> r >> q;
    cin >> H[1];
    for(int i = 2; i <= n; i++){
        int p;
        cin >> p >> H[i];
        g[p].push_back(i);
    }
    dfs(1);
    for(int i = 1; i <= r; i++){
        if(cnt[i] >= blsz){
            bigcnt++;
            assert(bigcnt < blsz);
            bigid[i] = bigcnt;
            dfs_calc(1, i, 0);
        }
    }
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        if(cnt[r1] >= blsz)cout << bigans[bigid[r1]][r2] << endl;
        else {
            int ptr1 = 0, ptr2 = 0, dep = 0, ans = 0;
            while(ptr1 < euler[r1].size() && ptr2 < euler[r2].size()){
                if(euler[r1][ptr1].first < euler[r2][ptr2].first){
                    dep += euler[r1][ptr1++].second;
                }
                else {
                    if(euler[r2][ptr2++].second == 1)ans += dep;
                }
            }
            cout << ans << endl;
        }
    }
}

Compilation message (stderr)

regions.cpp: In function 'void dfs_calc(int, int, int)':
regions.cpp:30:14: warning: unused variable 'v' [-Wunused-variable]
   30 |     for(auto v: g[x])dfs_calc(x, id, dep);
      |              ^
regions.cpp: In function 'int main()':
regions.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             while(ptr1 < euler[r1].size() && ptr2 < euler[r2].size()){
      |                   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:56:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             while(ptr1 < euler[r1].size() && ptr2 < euler[r2].size()){
      |                                              ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 85