Submission #1245477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245477		KALARRY	Regions (IOI09_regions)	C++20	25 / 100	8096 ms	46460 KiB

regions

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int S = 400;

int N,R,Q,x[200005],pushed[200005],par[200005],tin[200005],tout[200005],timer,st[800005],lazy[800005],up[450][25005],down[450][25005],s[200005];
pair<int,int> temp[200005];
vector<int> adj[200005];
vector<int> 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;
    for(auto u : adj[v])
        if(u != p)
            dfs(u,v);
    tout[v] = timer;
}

void propagate(int v,int start,int end);

void update(int l,int r,int val,int v = 1,int start = 1,int end = N)
{
    if(start==l && end==r)
    {
        st[v] += (end - start + 1) * val;
        lazy[v] += val;
        return;
    }
    propagate(v,start,end);
    int mid = (start + end)/2;
    if(r <= mid)
        update(l,r,val,2*v,start,mid);
    else if(l > mid)
        update(l,r,val,2*v+1,mid+1,end);
    else
    {
        update(l,mid,val,2*v,start,mid);
        update(mid+1,r,val,2*v+1,mid+1,end);
    }
    st[v] = st[2*v] + st[2*v+1];
}

void propagate(int v,int start,int end)
{
    if(lazy[v])
    {
        int mid = (start + end)/2;
        update(start,mid,lazy[v],2*v,start,mid);
        update(mid+1,end,lazy[v],2*v+1,mid+1,end);
        lazy[v] = 0;
    }
}

void activate_node(int v)
{
    update(tin[v],tout[v],1);
}

void deactivate_node(int v)
{
    update(tin[v],tout[v],-1);
}

int query(int pos,int v = 1,int start = 1,int end = N)
{
    if(start==end)
        return st[v];
    propagate(v,start,end);
    int mid = (start + end)/2;
    if(pos <= mid)
        return query(pos,2*v,start,mid);
    else
        return query(pos,2*v+1,mid+1,end);
}

int cur_cost(int v)
{
    return query(tin[v]);
}

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

void precompute(int r)
{
    for(auto v : nodes[r])
        activate_node(v);   
    for(int i = 1 ; i <= N ; i++)
        up[r][x[i]] += cur_cost(i);
    for(auto v : nodes[r])
        deactivate_node(v);

    for(auto x : nodes[r])
        s[x] = 1;
    dfs2(1,1,r);
    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 if(nodes[b].size() >= S)
            ans = down[b][a];
        else
        {
            for(auto v : nodes[a])
                activate_node(v);
            for(auto u : nodes[b])
                ans += cur_cost(u);
        }
        printf("%d\n",ans);
        fflush(stdout);
        for(auto v : nodes[a])
            deactivate_node(v);
    }
    return 0;
}

Compilation message (stderr)

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

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