Submission #521614

#	Time	Username	Problem	Language	Result	Execution time	Memory
521614		andrei_boaca	Regions (IOI09_regions)	C++14	100 / 100	2424 ms	122516 KiB

regions

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> muchii[200005];
vector<int> members[25005];
vector<int> freq;
struct date
{
    int poz,add;
};
vector<date> ev[25005];
int nrm[25005];
int reg[200005];
int n,r,q;
int cnt=0;
int par[200005];
int up[25005][455],down[25005][455];
ll special[455][455];
bool isfr[25005];
int in[200005],out[200005],timp;
int f[25005];
int jos;
int nr[200005];
void dfs(int nod)
{
    timp++;
    in[nod]=timp;
    f[reg[nod]]++;
    for(int i:freq)
    {
        if(isfr[reg[nod]])
            special[nrm[i]][nrm[reg[nod]]]+=f[i];
        else
            up[reg[nod]][nrm[i]]+=f[i];
    }
    for(int i:muchii[nod])
        dfs(i);
    f[reg[nod]]--;
    timp++;
    out[nod]=timp;
}
void build(int nod)
{
    nr[nod]=(reg[nod]==jos);
    for(int i:muchii[nod])
    {
        build(i);
        nr[nod]+=nr[i];
    }
    down[reg[nod]][nrm[jos]]+=nr[nod];
}
bool comp(date a, date b)
{
    return a.poz<b.poz;
}
int main()
{
    cin>>n>>r>>q;
    cin>>reg[1];
    members[reg[1]].push_back(1);
    for(int i=2;i<=n;i++)
    {
        cin>>par[i];
        cin>>reg[i];
        muchii[par[i]].push_back(i);
        members[reg[i]].push_back(i);
    }
    for(int i=1;i<=r;i++)
    {
        if(members[i].size()>=500)
        {
            isfr[i]=1;
            freq.push_back(i);
            cnt++;
            nrm[i]=cnt;
        }
        else
            isfr[i]=0;
    }
    dfs(1);
    for(int i:freq)
    {
        jos=i;
        build(1);
    }
    for(int i=1;i<=r;i++)
    {
        for(int j:members[i])
        {
            ev[i].push_back({in[j]-1,-1});
            ev[i].push_back({out[j],+1});
        }
        sort(ev[i].begin(),ev[i].end(),comp);
    }
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(isfr[r1]&&isfr[r2])
        {
            cout<<special[nrm[r1]][nrm[r2]]<<endl;
            continue;
        }
        if(isfr[r1])
        {
            cout<<up[r2][nrm[r1]]<<endl;
            continue;
        }
        if(isfr[r2])
        {
            cout<<down[r1][nrm[r2]]<<endl;
            continue;
        }
        int j=0;
        int s=0;
        ll ans=0;
        for(date i:ev[r1])
        {
            while(j<ev[r2].size()&&ev[r2][j].poz<=i.poz)
                {
                    if(ev[r2][j].add==1)
                        s++;
                    j++;
                }
            ans+=s*i.add;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             while(j<ev[r2].size()&&ev[r2][j].poz<=i.poz)
      |                   ~^~~~~~~~~~~~~~

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