Submission #1228713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228713		minhpk	Regions (IOI09_regions)	C++20	100 / 100	3159 ms	35856 KiB

regions

#include <bits/stdc++.h>

using namespace std;
int a,b,c;
int t[200001];
int block;
vector <int> z[200001];
int sta[200001];
int fin[200001];
int tour;
int sl[200001];
int cnt[501][25001];
int mark[200001];
int cur;
vector <int> heavy;
vector <int> pre[200001];
vector <int> pos[200001];
int dem[200001];
void dfs(int i){
    tour++;
    sta[i]=tour;
    pre[t[i]].push_back(sta[i]);
    for (auto p:heavy){
         cnt[mark[p]][t[i]]+=dem[p];
    }
    dem[t[i]]++;
    for (auto p:z[i]){
         dfs(p);
    }
    dem[t[i]]--;
    fin[i]=tour;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> a >> b >> c;
    block=500;
    cin >> t[1];
    sl[t[1]]++;
    pos[t[1]].push_back(1);

    for (int i=2;i<=a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(i);
         sl[y]++;
         t[i]=y;
         pos[y].push_back(i);
    }
    for (int i=1;i<=a;i++){
         if (sl[i]>=block){
             cur++;
             mark[i]=cur;
             heavy.push_back(i);
         }
    }
    dfs(1);
    while (c--){
         int x,y;
         cin >> x >> y;
         if (mark[x]){
             cout << cnt[mark[x]][y] << "\n";
         }else{
             int res=0;
             for (auto p:pos[x]){
                  int  l=lower_bound(pre[y].begin(),pre[y].end(),sta[p])-pre[y].begin();
                  int  r=upper_bound(pre[y].begin(),pre[y].end(),fin[p])-pre[y].begin();
                  res+=r-l;
             }
             cout << res << "\n";
         }
         cout << flush;
    }
    return 0;
}

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