Submission #57614

#	Time	Username	Problem	Language	Result	Execution time	Memory
57614		Bodo171	Regions (IOI09_regions)	C++14	100 / 100	3039 ms	35264 KiB

regions

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=200005;
const int rmax=25005;
const int K=500;//vezi aici
vector<int> v[nmax],in[nmax],out[nmax];
int Up[405][rmax],Down[405][rmax];
int ap[rmax],norm[rmax];
int lev[nmax],w[nmax],col[nmax];
int nr,n,reg,norms,r,q,i,tt,r1,r2;
void defeseu(int x)
{
    ++nr;
    in[col[x]].push_back(nr);
    for(int i=0;i<v[x].size();i++)
       defeseu(v[x][i]);
    out[col[x]].push_back(nr);
}
void dfs(int x)
{
    if(col[x]==reg) lev[x]++,w[x]++;
    for(int i=0;i<v[x].size();i++)
    {
        lev[v[x][i]]=lev[x];
        dfs(v[x][i]);
        w[x]+=w[v[x][i]];
    }
    Up[norms][col[x]]+=lev[x];
    Down[norms][col[x]]+=w[x];
}
int get_ans(int sef,int sub)
{
    int ret=0,p1=0,p2=0;
    for(int i=0;i<in[sub].size();i++)
    {
        while(p1<in[sef].size()&&in[sef][p1]<in[sub][i])
            p1++;
        while(p2<out[sef].size()&&out[sef][p2]<in[sub][i])
            p2++;
        ret+=(p1-p2);
    }
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>r>>q;
    cin>>col[1];
    for(i=2;i<=n;i++)
    {
        cin>>tt>>col[i];
        v[tt].push_back(i);
        ap[col[i]]++;
    }
    defeseu(1);
    for(reg=1;reg<=r;reg++)
        if(ap[reg]>=K)
    {
        for(i=1;i<=n;i++)
            lev[i]=w[i]=0;
        norm[reg]=++norms;
        dfs(1);
    }
    for(int cnt=1;cnt<=q;cnt++)
    {
        cin>>r1>>r2;
        if(ap[r1]>=K)
        {
            cout<<Up[norm[r1]][r2]<<'\n';
        }
        else
        {
            if(ap[r2]>=K)
            {
                cout<<Down[norm[r2]][r1]<<'\n';
            }
            else
                cout<<get_ans(r1,r2)<<'\n';
        }
        cout.flush();
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void defeseu(int)':
regions.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
regions.cpp: In function 'void dfs(int)':
regions.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
regions.cpp: In function 'int get_ans(int, int)':
regions.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<in[sub].size();i++)
                 ~^~~~~~~~~~~~~~~
regions.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p1<in[sef].size()&&in[sef][p1]<in[sub][i])
               ~~^~~~~~~~~~~~~~~
regions.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p2<out[sef].size()&&out[sef][p2]<in[sub][i])
               ~~^~~~~~~~~~~~~~~~

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