Submission #852547

#	Time	Username	Problem	Language	Result	Execution time	Memory
852547		abcvuitunggio	Regions (IOI09_regions)	C++17	5 / 100	7674 ms	131072 KiB

regions

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=58;
int n,R,q,r1,r2,cnt[200001][sz+1],c[25001][sz+1],c2[25001][sz+2],r[200001],p[200001],tin[200001],tout[200001],t;
vector <int> ke[200001],ve[25001];
void dfs(int u){
    tin[u]=++t;
    ve[r[u]].push_back(t);
    if (r[u]<=sz)
        cnt[u][r[u]]++;
    for (int v:ke[u]){
        for (int i=1;i<=sz;i++)
            cnt[v][i]+=cnt[u][i];
        dfs(v);
    }
    for (int i=1;i<=sz;i++)
        c[r[u]][i]+=cnt[u][i];
    tout[u]=++t;
    ve[r[u]].push_back(-t);
}
void dfs2(int u){
    if (r[u]<=sz)
        cnt[u][r[u]]++;
    for (int v:ke[u]){
        dfs2(v);
        for (int i=1;i<=sz;i++)
            cnt[v][i]+=cnt[u][i];
    }
    for (int i=1;i<=sz;i++)
        c2[r[u]][i]+=cnt[u][i];
    tout[u]=++t;
    ve[r[u]].push_back(-t);
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> R >> q;
    for (int i=1;i<=n;i++){
        if (i>1){
            cin >> p[i];
            ke[p[i]].push_back(i);
        }
        cin >> r[i];
    }
    dfs(1);
    memset(cnt,0,sizeof(cnt));
    dfs2(1);
    while (q--){
        cin >> r1 >> r2;
        if (r1<=sz){
            cout << c[r2][r1] << endl;
            continue;
        }
        if (r2<=sz){
            cout << c2[r1][r2] << endl;
            continue;
        }
        int j=0,cnt=0,res=0;
        for (int i=0;i<ve[r2].size();i++){
            while (j<ve[r1].size()){
                if (abs(ve[r1][j])>abs(ve[r2][i]))
                    break;
                cnt+=(ve[r1][j]>0)-(ve[r1][j]<0);
                j++;
            }
            if (ve[r2][i]>0)
                res+=cnt;
        }
        cout << res << endl;
    }
}

Compilation message (stderr)

regions.cpp: In function 'int32_t main()':
regions.cpp:59:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int i=0;i<ve[r2].size();i++){
      |                      ~^~~~~~~~~~~~~~
regions.cpp:60:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

• Subtask 1: 5 / 15
• Subtask 2: 0 / 85