Submission #1245169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245169		KALARRY	Regions (IOI09_regions)	C++20	0 / 100	8089 ms	29408 KiB

regions

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int S = 500;

int N,R,Q,x[200005],pushed[200005],par[200005],tin[200005],tout[200005],timer,st[800005],lazy[800005];
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 <= R ; 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]);
}

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 a,b,i = 1 ; i <= Q ; i++)
    {
        scanf("%d%d",&a,&b);
        a = pushed[a];
        b = pushed[b];
        for(auto v : nodes[a])
            activate_node(v);
        int ans = 0;
        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:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d%d%d",&N,&R,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     scanf("%d",&x[1]);
      |     ~~~~~^~~~~~~~~~~~
regions.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         scanf("%d%d",&par[i],&x[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

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