oj.uz

Submission #57614

# Submission time Handle Problem Language Result Execution time Memory
57614 2018-07-15T12:35:26 Z Bodo171 Regions (IOI09_regions) C++14
100 / 100
 3039 ms 35264 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14332 KB Output is correct
2 Correct 18 ms 14388 KB Output is correct
3 Correct 18 ms 14424 KB Output is correct
4 Correct 20 ms 14500 KB Output is correct
5 Correct 20 ms 14576 KB Output is correct
6 Correct 48 ms 14576 KB Output is correct
7 Correct 49 ms 14704 KB Output is correct
8 Correct 62 ms 14752 KB Output is correct
9 Correct 65 ms 15164 KB Output is correct
10 Correct 128 ms 15164 KB Output is correct
11 Correct 168 ms 15292 KB Output is correct
12 Correct 194 ms 15676 KB Output is correct
13 Correct 155 ms 15676 KB Output is correct
14 Correct 288 ms 15932 KB Output is correct
15 Correct 267 ms 17852 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 19128 KB Output is correct
2 Correct 1167 ms 19128 KB Output is correct
3 Correct 1645 ms 20668 KB Output is correct
4 Correct 321 ms 20668 KB Output is correct
5 Correct 298 ms 20668 KB Output is correct
6 Correct 890 ms 20668 KB Output is correct
7 Correct 1249 ms 20668 KB Output is correct
8 Correct 1158 ms 22844 KB Output is correct
9 Correct 1663 ms 22844 KB Output is correct
10 Correct 2937 ms 26408 KB Output is correct
11 Correct 3039 ms 26408 KB Output is correct
12 Correct 1276 ms 26408 KB Output is correct
13 Correct 1640 ms 26408 KB Output is correct
14 Correct 2829 ms 29052 KB Output is correct
15 Correct 2608 ms 29216 KB Output is correct
16 Correct 2731 ms 32668 KB Output is correct
17 Correct 2515 ms 35264 KB Output is correct