oj.uz

Submission #835108

# Submission time Handle Problem Language Result Execution time Memory
835108 2023-08-23T08:29:31 Z Denkata Regions (IOI09_regions) C++17
0 / 100
 73 ms 26864 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int crit = 447;
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)
{
    cout<<i<<" "<<nom[i]<<" "<<type[u]<<" "<<cur<<endl;
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 6096 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 6096 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6224 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6224 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 6736 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 6736 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 6992 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 7504 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 7120 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 7760 KB Time limit exceeded (wall clock)
15 Execution timed out 15 ms 10304 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 18 ms 10832 KB Time limit exceeded (wall clock)
2 Execution timed out 22 ms 9692 KB Time limit exceeded (wall clock)
3 Execution timed out 20 ms 12728 KB Time limit exceeded (wall clock)
4 Execution timed out 13 ms 7840 KB Time limit exceeded (wall clock)
5 Execution timed out 12 ms 9424 KB Time limit exceeded (wall clock)
6 Execution timed out 17 ms 9136 KB Time limit exceeded (wall clock)
7 Execution timed out 21 ms 10320 KB Time limit exceeded (wall clock)
8 Execution timed out 26 ms 15200 KB Time limit exceeded (wall clock)
9 Execution timed out 49 ms 15680 KB Time limit exceeded (wall clock)
10 Execution timed out 50 ms 20800 KB Time limit exceeded (wall clock)
11 Execution timed out 60 ms 15548 KB Time limit exceeded (wall clock)
12 Execution timed out 57 ms 17004 KB Time limit exceeded (wall clock)
13 Execution timed out 57 ms 17216 KB Time limit exceeded (wall clock)
14 Execution timed out 73 ms 17100 KB Time limit exceeded (wall clock)
15 Execution timed out 55 ms 21560 KB Time limit exceeded (wall clock)
16 Execution timed out 72 ms 26864 KB Time limit exceeded (wall clock)
17 Execution timed out 55 ms 25556 KB Time limit exceeded (wall clock)