oj.uz

Submission #593360

# Submission time Handle Problem Language Result Execution time Memory
593360 2022-07-11T00:37:58 Z Bench0310 Regions (IOI09_regions) C++17
100 / 100
 2648 ms 33612 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=200005;
const int R=25005;
const int S=105;
const int BIG=N/S;
vector<int> v[N];
int h[N];
vector<int> region[R];
int all[R];
int tcnt=0;
int tin[N];
int tout[N];
vector<int> down[R];
vector<array<int,2>> up[R];
int bigres[BIG][BIG];
vector<int> big;
int bigid[R];
int cnt[R];
int bigcnt=0;

void add_up(int r,int t,int d)
{
    auto [pt,ps]=up[r].back();
    if(pt==t) up[r].back()[1]+=d;
    else up[r].push_back({t,ps+d});
}

void dfs(int a)
{
    tin[a]=tcnt++;
    down[h[a]].push_back(tin[a]);
    add_up(h[a],tin[a],1);
    if(bigid[h[a]]!=-1)
    {
        for(int r:big) bigres[bigid[r]][bigid[h[a]]]+=cnt[r];
    }
    cnt[h[a]]++;
    for(int to:v[a]) dfs(to);
    tout[a]=tcnt-1;
    add_up(h[a],tout[a]+1,-1);
    cnt[h[a]]--;
}

int qdown(int x,int l,int r)
{
    return upper_bound(down[x].begin(),down[x].end(),r)-lower_bound(down[x].begin(),down[x].end(),l);
}

int qup(int x,int t)
{
    auto it=lower_bound(up[x].begin(),up[x].end(),array<int,2>{t+1,0});
    return (*prev(it))[1];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,r,q;
    cin >> n >> r >> q;
    for(int i=1;i<=r;i++) up[i].push_back({-1,0});
    for(int i=1;i<=n;i++)
    {
        if(i>=2)
        {
            int p;
            cin >> p;
            v[p].push_back(i);
        }
        cin >> h[i];
        region[h[i]].push_back(i);
        all[h[i]]++;
    }
    for(int i=1;i<=r;i++)
    {
        bigid[i]=-1;
        if(all[i]>=S)
        {
            big.push_back(i);
            bigid[i]=bigcnt++;
        }
    }
    dfs(1);
    while(q--)
    {
        int a,b;
        cin >> a >> b;
        int res=0;
        if(all[a]>=S&&all[b]>=S) res=bigres[bigid[a]][bigid[b]];
        else if(all[a]<S)
        {
            for(int x:region[a]) res+=qdown(b,tin[x],tout[x]);
        }
        else if(all[b]<S)
        {
            for(int x:region[b]) res+=qup(a,tin[x]);
        }
        cout << res << endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6708 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 4 ms 6736 KB Output is correct
4 Correct 7 ms 6736 KB Output is correct
5 Correct 11 ms 6804 KB Output is correct
6 Correct 20 ms 6864 KB Output is correct
7 Correct 30 ms 6864 KB Output is correct
8 Correct 34 ms 6992 KB Output is correct
9 Correct 48 ms 7376 KB Output is correct
10 Correct 87 ms 7608 KB Output is correct
11 Correct 119 ms 7888 KB Output is correct
12 Correct 131 ms 8584 KB Output is correct
13 Correct 176 ms 8648 KB Output is correct
14 Correct 175 ms 10184 KB Output is correct
15 Correct 223 ms 12644 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 13676 KB Output is correct
2 Correct 914 ms 12704 KB Output is correct
3 Correct 1317 ms 16120 KB Output is correct
4 Correct 268 ms 9888 KB Output is correct
5 Correct 360 ms 11180 KB Output is correct
6 Correct 514 ms 11276 KB Output is correct
7 Correct 978 ms 13160 KB Output is correct
8 Correct 1093 ms 18876 KB Output is correct
9 Correct 1822 ms 24864 KB Output is correct
10 Correct 2301 ms 29588 KB Output is correct
11 Correct 2648 ms 25732 KB Output is correct
12 Correct 1523 ms 26092 KB Output is correct
13 Correct 1915 ms 26036 KB Output is correct
14 Correct 2136 ms 25648 KB Output is correct
15 Correct 2558 ms 31040 KB Output is correct
16 Correct 2495 ms 33612 KB Output is correct
17 Correct 1860 ms 32924 KB Output is correct