oj.uz

Submission #1086003

# Submission time Handle Problem Language Result Execution time Memory
1086003 2024-09-09T09:30:22 Z serkanrashid Regions (IOI09_regions) C++14
100 / 100
 3031 ms 31532 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10840 KB Output is correct
2 Correct 6 ms 10840 KB Output is correct
3 Correct 7 ms 10840 KB Output is correct
4 Correct 8 ms 10912 KB Output is correct
5 Correct 10 ms 10840 KB Output is correct
6 Correct 15 ms 10896 KB Output is correct
7 Correct 22 ms 11096 KB Output is correct
8 Correct 22 ms 11096 KB Output is correct
9 Correct 33 ms 11352 KB Output is correct
10 Correct 48 ms 11352 KB Output is correct
11 Correct 90 ms 11864 KB Output is correct
12 Correct 95 ms 12120 KB Output is correct
13 Correct 113 ms 11900 KB Output is correct
14 Correct 170 ms 12376 KB Output is correct
15 Correct 209 ms 14944 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1581 ms 15688 KB Output is correct
2 Correct 1790 ms 14508 KB Output is correct
3 Correct 2449 ms 17460 KB Output is correct
4 Correct 176 ms 12448 KB Output is correct
5 Correct 237 ms 14040 KB Output is correct
6 Correct 365 ms 15628 KB Output is correct
7 Correct 1210 ms 15248 KB Output is correct
8 Correct 769 ms 24124 KB Output is correct
9 Correct 1750 ms 19792 KB Output is correct
10 Correct 3007 ms 29884 KB Output is correct
11 Correct 3031 ms 19544 KB Output is correct
12 Correct 1012 ms 21192 KB Output is correct
13 Correct 1469 ms 21456 KB Output is correct
14 Correct 1811 ms 23004 KB Output is correct
15 Correct 2522 ms 25560 KB Output is correct
16 Correct 2699 ms 30832 KB Output is correct
17 Correct 2501 ms 31532 KB Output is correct