Submission #925231

#	Time	Username	Problem	Language	Result	Execution time	Memory
925231		ibm2006	Regions (IOI09_regions)	C++17	45 / 100	8084 ms	131072 KiB

regions

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],le[1100000],ri[1100000],h[1100000],q,m,ee;
pair<ll,ll> p;
vector<pair<ll,ll>> u[1100000],vv;
vector<ll> uu[1100000],v[1100000],uv[1100000];
void dfs(ll x,ll y)
{
    ll i;
    le[x]=t;
    t++;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        dfs(v[x][i],x);
    }
    ri[x]=t;
    t++;
}
int main()
{
    scanf("%lld %lld %lld",&n,&m,&q);
    for(i=1;i<=n;i++)
    {
        if(i==1)
        {
            scanf("%lld",&x);
            a[i]=x;
            uv[a[i]].push_back(i);
            continue;
        }
        scanf("%lld %lld",&x,&y);
        a[i]=y;
        uv[a[i]].push_back(i);
        v[x].push_back(i);
        v[i].push_back(x);
        h[x]++;
        h[i]++;
    }
    t=1;
    dfs(1,0);
    for(i=1;i<=n;i++)
    {
        u[a[i]].push_back({le[i],1});
        u[a[i]].push_back({ri[i],-1});
        uu[a[i]].push_back(le[i]);
        b[a[i]]++;
    }
    for(i=1;i<=m;i++)
    {
        sort(u[i].begin(),u[i].end());
        vv.clear();
        s=0;
        for(j=0;j<u[i].size();j++)
        {
            p=u[i][j];
            s+=p.second;
            vv.push_back({p.first,s});
        }
        u[i].clear();
        for(j=0;j<vv.size();j++)
        {
            if(j+1==vv.size())
            {
                u[i].push_back(vv[j]);
                continue;
            }
            if(vv[j].first!=vv[j+1].first)
                u[i].push_back(vv[j]);
        }
        sort(uu[i].begin(),uu[i].end());
    }
    for(i=1;i<=n;i++)
    {
     //   printf("%lld:%lld %lld %lld\n",i,a[i],le[i],ri[i]);
    }
    for(ee=0;ee<q;ee++)
    {
        s=0;
        scanf("%lld %lld",&x,&y);
        if(b[x]<b[y])
        {
            for(i=0;i<uv[x].size();i++)
            {
                z=uv[x][i];
                //printf("(%lld,%lld)\n",z,s);
                s+=lower_bound(uu[y].begin(),uu[y].end(),ri[z])-lower_bound(uu[y].begin(),uu[y].end(),le[z]);
            }
            printf("%lld\n",s);
            fflush(stdout);
            continue;
        }
        for(i=0;i<uv[y].size();i++)
        {
            z=uv[y][i];
            //printf("(%lld,%lld)\n",z,s);
            w=lower_bound(u[x].begin(),u[x].end(),make_pair(le[z],ll(0)))-u[x].begin();
            w--;
            if(w>=0)
            s+=u[x][w].second;
        }
        printf("%lld\n",s);
        fflush(stdout);
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:56:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(j=0;j<u[i].size();j++)
      |                 ~^~~~~~~~~~~~
regions.cpp:63:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(j=0;j<vv.size();j++)
      |                 ~^~~~~~~~~~
regions.cpp:65:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if(j+1==vv.size())
      |                ~~~^~~~~~~~~~~
regions.cpp:85:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(i=0;i<uv[x].size();i++)
      |                     ~^~~~~~~~~~~~~
regions.cpp:95:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(i=0;i<uv[y].size();i++)
      |                 ~^~~~~~~~~~~~~
regions.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%lld %lld %lld",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:29:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |             scanf("%lld",&x);
      |             ~~~~~^~~~~~~~~~~
regions.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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