Submission #869056

#	Time	Username	Problem	Language	Result	Execution time	Memory
869056		HuyQuang_re_Zero	Regions (IOI09_regions)	C++14	100 / 100	1564 ms	62736 KiB

regions

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
int par[451][25001],child[451][25001],n,m,q,type[N],k,k1,k2,i,u,v,l[N],r[N],now,cnt[N],num[N],f[N],sz[N],root;
vector <int> pos[N],big,a[N];
vector <II> seg[N];
void dfs(int u)
{
    cnt[type[u]]++;
    l[u]=++now;
    for(int k:big) par[num[k]][type[u]]+=cnt[k];
    for(int v:a[u]) dfs(v);
    cnt[type[u]]--;


    r[u]=now;
    pos[type[u]].push_back(l[u]);
    seg[type[u]].push_back({ l[u]-1,-1 });
    seg[type[u]].push_back({ r[u],1 });
}

void DFS(int u,int k)
{
    f[u]=(type[u]==k);
    for(int v:a[u]) DFS(v,k),f[u]+=f[v];
    child[num[k]][type[u]]+=f[u];
}
int main()
{
  //  freopen("regions.inp","r",stdin);
    //freopen("regions.out","w",stdout);
  //  ios_base::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    cin>>type[1];
    for(i=2;i<=n;i++) cin>>u>>type[i],a[u].push_back(i),sz[type[i]]++;
    root=trunc(sqrt(n));
    for(k=1;k<=m;k++)
        if(sz[k]>root) big.push_back(k),num[k]=big.size();
    dfs(1);
    for(int k:big) DFS(1,k);
    for(k=1;k<=m;k++)
    {
        sort(pos[k].begin(),pos[k].end());
        sort(seg[k].begin(),seg[k].end());
    }

    while(q--)
    {
        cin>>k1>>k2;
        if(sz[k1]>root) cout<<par[num[k1]][k2]<<'\n';
        else if(sz[k2]>root) cout<<child[num[k2]][k1]<<'\n';
        else
        {
            int j=0,res=0;
            for(II x:seg[k1])
            {
                while(j<pos[k2].size() && pos[k2][j]<=x.fst) j++;
                res+=j*x.snd;
            }
            cout<<res<<'\n';
        }
        fflush(stdout);
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 while(j<pos[k2].size() && pos[k2][j]<=x.fst) j++;
      |                       ~^~~~~~~~~~~~~~~

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