Submission #1086003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086003		serkanrashid	Regions (IOI09_regions)	C++14	100 / 100	3031 ms	31532 KiB

regions

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

const int GR = 450;
const int MAXN = 2e5+5;
const int MAXR = 25*1e4+5;

int n,r,q;
int h[MAXN],p[MAXN];
vector<int>g[MAXN];

int Time;
int in[MAXN],ou[MAXN];
vector<int>ver[MAXR];

map<int,int>mymap;
int idx,br[GR+1][MAXR];

int get_map(int x)
{
    if(!mymap[x]) mymap[x] = ++idx;
    return mymap[x];
}

void dfs_small(int beg, int par)
{
    ver[h[beg]].push_back(beg);
    in[beg] = ++Time;
    for(int nb : g[beg]) dfs_small(nb,beg);
    ou[beg] = Time;
}

int s1,s2,ans;
int pom;

void dfs(int beg, int par, int br1)
{
    if(h[beg]!=s1) br[pom][h[beg]] += br1;
    if(h[beg]==s1) br1++;
    for(int nb : g[beg]) dfs(nb,beg,br1);
}

int bin_s(int x)
{
    if(x==0) return 0;
    int l = 0, r = ver[s2].size()-1;
    int mid;
    while(l<=r)
    {
        mid = (l+r)/2;
        if(in[ver[s2][mid]] <= x) l = mid+1;
        else r = mid-1;
    }
    return r+1;///indexirane ot 0
}

void read()
{
    cin >> n >> r >> q;
    cin >> h[1];
    for(int i = 2; i <= n; i++)
    {
        cin >> p[i] >> h[i];
        g[p[i]].push_back(i);
    }
    dfs_small(1,1);
    for(int i = 1; i <= r; i++)
    {
        s1 = i;
        if(ver[s1].size()<=GR) continue;
        pom = get_map(s1);
        dfs(1,1,0);
    }
    for(int i = 1; i <= q; i++)
    {
        ans = 0;
        cin >> s1 >> s2;
        if(ver[s1].size()<=GR)
        {
            for(int v : ver[s1])
            {
                int ql = in[v];
                int qr = ou[v];
                ans += bin_s(qr);
                ans -= bin_s(ql-1);
            }
            cout << ans << endl;
        }
        else
        {
            pom = get_map(s1);
            cout << br[pom][s2] << endl;
        }
        cout.flush();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    return 0;
}

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