Submission #1246006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246006		KALARRY	Regions (IOI09_regions)	C++20	100 / 100	3044 ms	26524 KiB

regions

//chockolateman
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include<bits/stdc++.h>

using namespace std;

const int S = 447;

int N,R,Q,x[200005],pushed[200005],par[200005],tin[200005],tout[200005],timer,st[800005],lazy[800005],up[450][25005],s[200005];
pair<int,int> temp[200005];
vector<int> adj[200005];
vector<int> nodes[25005];
vector<int> tin_nodes[25005];

void coordinate_compression()
{
    for(int i = 1 ; i <= R ; i++)
        temp[i].second = i;
    for(int i = 1 ; i <= N ; i++)
        temp[x[i]].first++;
    sort(temp+1,temp+R+1,greater<pair<int,int>>());    
    int counter =0;
    for(int i = 1 ; i <= R ; i++)
    {
        if(temp[i].first==0)
            continue;
        counter++;
        pushed[temp[i].second] = counter;
    }
    for(int i = 1 ; i <= N ; i++)
    {
        x[i] = pushed[x[i]];
        nodes[x[i]].push_back(i);
    }
}

void dfs(int v,int p)
{
    tin[v] = ++timer;
    tin_nodes[x[v]].push_back(tin[v]);
    for(auto u : adj[v])
        if(u != p)
            dfs(u,v);
    tout[v] = timer;
}

void dfs2(int v,int p,int r,int counter)
{
    if(s[v]==1)
        counter++;
    up[r][x[v]]+=counter;
    for(auto u : adj[v])
        if(u != p)
            dfs2(u,v,r,counter);
}

void precompute(int r)
{
    for(auto x : nodes[r])
        s[x] = 1;
    dfs2(1,1,r,0);
    for(int i = 1 ; i <= N ; i++)
        s[i] = 0;
}

int main()
{
    scanf("%d%d%d",&N,&R,&Q);
    par[1] = 1;
    scanf("%d",&x[1]);
    for(int i = 2 ; i <= N ; i++)
    {
        scanf("%d%d",&par[i],&x[i]);
        adj[par[i]].push_back(i);
        adj[i].push_back(par[i]);
    }
    coordinate_compression();
    dfs(1,1);
    for(int i = 1 ; i <= R ; i++)
        if(nodes[i].size() >= S)
            precompute(i);
    for(int a,b,i = 1 ; i <= Q ; i++)
    {
        scanf("%d%d",&a,&b);
        a = pushed[a];
        b = pushed[b];
        int ans = 0;
        if(nodes[a].size() >= S)
            ans = up[a][b];
        else
            for(auto v : nodes[a])
                ans += upper_bound(tin_nodes[b].begin(),tin_nodes[b].end(),tout[v]) - upper_bound(tin_nodes[b].begin(),tin_nodes[b].end(),tin[v]);
        printf("%d\n",ans);
        fflush(stdout);

    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d%d%d",&N,&R,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d",&x[1]);
      |     ~~~~~^~~~~~~~~~~~
regions.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d%d",&par[i],&x[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

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