oj.uz

Submission #593359

# Submission time Handle Problem Language Result Execution time Memory
593359 2022-07-10T23:54:58 Z Bench0310 Regions (IOI09_regions) C++17
30 / 100
 2517 ms 41348 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)
{
    up[r].push_back({t,up[r].back()[1]+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);
    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 6736 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 5 ms 6736 KB Output is correct
4 Correct 5 ms 6736 KB Output is correct
5 Correct 8 ms 6860 KB Output is correct
6 Correct 20 ms 6864 KB Output is correct
7 Correct 27 ms 6864 KB Output is correct
8 Correct 38 ms 6992 KB Output is correct
9 Correct 24 ms 7632 KB Output is correct
10 Correct 72 ms 7508 KB Output is correct
11 Correct 122 ms 8044 KB Output is correct
12 Correct 102 ms 8844 KB Output is correct
13 Correct 182 ms 8604 KB Output is correct
14 Correct 177 ms 10236 KB Output is correct
15 Correct 221 ms 14408 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 14432 KB Output is correct
2 Incorrect 879 ms 12916 KB Output isn't correct
3 Correct 1382 ms 17544 KB Output is correct
4 Incorrect 254 ms 9928 KB Output isn't correct
5 Incorrect 199 ms 12096 KB Output isn't correct
6 Incorrect 592 ms 11412 KB Output isn't correct
7 Incorrect 910 ms 13384 KB Output isn't correct
8 Incorrect 1081 ms 21244 KB Output isn't correct
9 Incorrect 1716 ms 25468 KB Output isn't correct
10 Incorrect 2125 ms 32072 KB Output isn't correct
11 Correct 2517 ms 26024 KB Output is correct
12 Incorrect 1518 ms 26064 KB Output isn't correct
13 Incorrect 1675 ms 26772 KB Output isn't correct
14 Incorrect 1779 ms 25932 KB Output isn't correct
15 Incorrect 2260 ms 33224 KB Output isn't correct
16 Incorrect 2507 ms 41348 KB Output isn't correct
17 Incorrect 1780 ms 39616 KB Output isn't correct