oj.uz

Submission #835116

# Submission time Handle Problem Language Result Execution time Memory
835116 2023-08-23T08:40:35 Z Denkata Regions (IOI09_regions) C++17
100 / 100
 4173 ms 27420 KB 
#include<bits/stdc++.h>
using namespace std;
const int crit = 450;
const int maxn = 2e5+3;
const int maxr = 25003;
int i,j,p,q,n,m,R,Q,k,tin[maxn],tout[maxn],br,cnt[crit+3][maxr],hora[maxn],type[maxn],cur,d,nom[maxn];
vector <int> v[maxn];
vector <int> vid[maxr];
vector <int> kraishta[maxr];
void dfs(int u)
{
    tin[u]=++br;
    for(auto i:v[u])
        dfs(i);
    tout[u]=++br;
    kraishta[type[u]].push_back(tin[u]);
}
void dfs2(int u)
{
    cnt[nom[i]][type[u]]+=cur;
    if(type[u]==i)
        cur++;
    for(auto j:v[u])
        dfs2(j);
    if(type[u]==i)
        cur--;
}
int calc()
{
    int ans = 0;
    for(auto i:vid[p])
    {
        int l = lower_bound(kraishta[q].begin(),kraishta[q].end(),tin[i]) - kraishta[q].begin();
        int r = lower_bound(kraishta[q].begin(),kraishta[q].end(),tout[i]+1) - kraishta[q].begin() - 1;
        //cout<<i<<" "<<tin[i]<<" "<<tout[i]<<" "<<l<<" "<<r<<" "<<kraishta[q][l]<<" "<<kraishta[q][r]<<endl;
        if(l>r)continue;  
        l = max(0,l);l = min(l,(int)kraishta[q].size()-1);
        r = max(0,r);r = min(r,(int)kraishta[q].size()-1);    
        ans+=r-l+1;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>R>>Q;
    cin>>p;
    hora[p]++;type[1] = p;vid[p].push_back(1);
    for(i=2;i<=n;i++)
    {
        cin>>p>>q;
        hora[q]++;
        type[i] = q;
        vid[q].push_back(i);
        v[p].push_back(i);
    }
    dfs(1);
    for(i=1;i<=R;i++)
    {
        if(hora[i]>=crit)
        {
           // cur = 0;
            nom[i]=++d;
            dfs2(1);
        }
    }
    for(i=1;i<=n;i++)
        sort(kraishta[i].begin(),kraishta[i].end());
    while(Q--)
    {
        cin>>p>>q;
        if(hora[p]>crit)
            cout<<cnt[nom[p]][q]<<endl;
        else
            cout<<calc()<<endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6096 KB Output is correct
2 Correct 3 ms 6224 KB Output is correct
3 Correct 4 ms 6224 KB Output is correct
4 Correct 4 ms 6224 KB Output is correct
5 Correct 8 ms 6224 KB Output is correct
6 Correct 21 ms 6224 KB Output is correct
7 Correct 26 ms 6224 KB Output is correct
8 Correct 26 ms 6224 KB Output is correct
9 Correct 49 ms 6736 KB Output is correct
10 Correct 69 ms 6736 KB Output is correct
11 Correct 117 ms 6992 KB Output is correct
12 Correct 120 ms 7548 KB Output is correct
13 Correct 138 ms 7248 KB Output is correct
14 Correct 267 ms 7760 KB Output is correct
15 Correct 262 ms 10304 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1674 ms 10928 KB Output is correct
2 Correct 2095 ms 9772 KB Output is correct
3 Correct 2595 ms 12732 KB Output is correct
4 Correct 190 ms 7888 KB Output is correct
5 Correct 322 ms 9424 KB Output is correct
6 Correct 491 ms 10988 KB Output is correct
7 Correct 1350 ms 10824 KB Output is correct
8 Correct 778 ms 19580 KB Output is correct
9 Correct 2238 ms 15632 KB Output is correct
10 Correct 3344 ms 26068 KB Output is correct
11 Correct 4173 ms 15612 KB Output is correct
12 Correct 1187 ms 17092 KB Output is correct
13 Correct 1898 ms 17264 KB Output is correct
14 Correct 1969 ms 18876 KB Output is correct
15 Correct 2746 ms 21628 KB Output is correct
16 Correct 2537 ms 26900 KB Output is correct
17 Correct 2564 ms 27420 KB Output is correct