Submission #852575

#	Time	Username	Problem	Language	Result	Execution time	Memory
852575		abcvuitunggio	Regions (IOI09_regions)	C++17	80 / 100	1684 ms	131072 KiB

regions

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=500;
int lim,n,R,q,r1,r2,cnt[25001],c[25001][200000/sz+1],c2[25001][200000/sz+1],sum[400001],r[200001],p[200001],tin[200001],tout[200001],t,C[25001],pos[25001];
vector <int> ke[200001],ve[25001],V;
void dfs(int u){
    tin[u]=++t;
    ve[r[u]].push_back(t);
    for (int i=1;i<=lim;i++)
        c[r[u]][i]+=cnt[i];
    if (C[r[u]]>sz)
        cnt[pos[r[u]]]++;
    for (int v:ke[u])
        dfs(v);
    tout[u]=++t;
    ve[r[u]].push_back(-t);
    if (C[r[u]]>sz)
        cnt[pos[r[u]]]--;
}
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];
        C[r[i]]++;
    }
    for (int i=1;i<=R;i++)
        V.push_back(i);
    sort(V.begin(),V.end(),[](int i, int j){return C[i]>C[j];});
    for (int i=0;i<V.size();i++){
        pos[V[i]]=i+1;
        if (C[V[i]]>sz)
            lim=i+1;
    }
    dfs(1);
    for (int i=1;i<=R;i++)
        if (C[i]>sz){
            memset(sum,0,sizeof(sum));
            for (int j:ve[i])
                if (j>0)
                    sum[j]++;
            for (int j=1;j<=n*2;j++)
                sum[j]+=sum[j-1];
            for (int j=1;j<=n;j++)
                c2[r[j]][pos[i]]+=sum[tout[j]]-sum[tin[j]-1];
        }
    while (q--){
        cin >> r1 >> r2;
        if (ve[r1].empty()||ve[r2].empty()){
            cout << 0 << endl;
            continue;
        }
        if (C[r1]>sz){
            cout << c[r2][pos[r1]] << endl;
            continue;
        }
        if (C[r2]>sz){
            cout << c2[r1][pos[r2]] << endl;
            continue;
        }
        int j=0,cnt=0,res=0;
        for (int i:ve[r2]){
            while (j<ve[r1].size()){
                if (abs(ve[r1][j])>abs(i))
                    break;
                cnt+=(ve[r1][j]>0)-(ve[r1][j]<0);
                j++;
            }
            if (i>0)
                res+=cnt;
        }
        cout << res << endl;
    }
}

Compilation message (stderr)

regions.cpp: In function 'int32_t main()':
regions.cpp:35:19: 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]
   35 |     for (int i=0;i<V.size();i++){
      |                  ~^~~~~~~~~
regions.cpp:68: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]
   68 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

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