Submission #1026970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026970		Summers	Regions (IOI09_regions)	C++14	100 / 100	3369 ms	120808 KiB

regions

#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<long long> v[1000000],d[1000000], ans[1000000],c[1000000];
long long t=1, p[1000000], tin[1000000], tout[1000000];
void dfs(long long vr)
{
    tin[vr]=t++;
    d[p[vr]].push_back(tin[vr]);
    for (int i=0;i<v[vr].size();i++)
    {
        dfs(v[vr][i]);
    }
    tout[vr]=t;
}

void dfs1(long long br, long long vr,long long val)
{
    if(val==p[vr])br++;
    else ans[val][p[vr]]+=br;

    for(int i=0;i<v[vr].size();i++)
    {
        dfs1(br, v[vr][i], val);
    }
}

int main()
{
    long long i,j,r,q,n,h,s,a,b;

    cin>>n>>r>>q;

    cin>>h;
    p[1]=h;
    c[h].push_back(1);

    for(i=2;i<=n;i++)
    {
        cin>>s>>h;
        p[i]=h;
        v[s].push_back(i);
        c[h].push_back(i);
    }
    dfs(1);

    for(i=1;i<=r;i++)
    {
        if(d[i].size()>=1000)
        {
            ans[i].resize(r+1);
            dfs1(0,1,i);
        }
    }

    while(q--)
    {
        cin>>a>>b;

        if(d[a].size()>=1000)
        {
            cout<<ans[a][b]<<endl;
            cout.flush();
        }
        else
        {
            long long an=0;
            for (long long i=0;i<c[a].size();i++)
            {
                auto it1 = upper_bound(d[b].begin(), d[b].end(), tout[c[a][i]]-1);
                it1--;
                auto it2 =lower_bound(d[b].begin(), d[b].end(), tin[c[a][i]]);

                an+=it1-it2+1;
            }

            cout<<an<<endl;
            cout.flush();
        }
    }
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(long long int)':
regions.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i=0;i<v[vr].size();i++)
      |                  ~^~~~~~~~~~~~~
regions.cpp: In function 'void dfs1(long long int, long long int, long long int)':
regions.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[vr].size();i++)
      |                 ~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:68:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for (long long i=0;i<c[a].size();i++)
      |                                ~^~~~~~~~~~~~
regions.cpp:30:17: warning: unused variable 'j' [-Wunused-variable]
   30 |     long long i,j,r,q,n,h,s,a,b;
      |                 ^

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