oj.uz

Submission #835109

# Submission time Handle Problem Language Result Execution time Memory
835109 2023-08-23T08:31:30 Z Denkata Regions (IOI09_regions) C++17
0 / 100
 79 ms 26768 KB 
#include<bits/stdc++.h>
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]<<flush;
        else
            cout<<calc()<<flush;
    }
    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 3 ms 6096 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
4 Execution timed out 3 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 3 ms 6216 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 8 ms 6992 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 7504 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 7248 KB Time limit exceeded (wall clock)
14 Execution timed out 11 ms 7816 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 10320 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 22 ms 10832 KB Time limit exceeded (wall clock)
2 Execution timed out 21 ms 9764 KB Time limit exceeded (wall clock)
3 Execution timed out 22 ms 12624 KB Time limit exceeded (wall clock)
4 Execution timed out 12 ms 7888 KB Time limit exceeded (wall clock)
5 Execution timed out 12 ms 9480 KB Time limit exceeded (wall clock)
6 Execution timed out 17 ms 9224 KB Time limit exceeded (wall clock)
7 Execution timed out 22 ms 10320 KB Time limit exceeded (wall clock)
8 Execution timed out 26 ms 15304 KB Time limit exceeded (wall clock)
9 Execution timed out 44 ms 15692 KB Time limit exceeded (wall clock)
10 Execution timed out 45 ms 20860 KB Time limit exceeded (wall clock)
11 Execution timed out 79 ms 15556 KB Time limit exceeded (wall clock)
12 Execution timed out 59 ms 16968 KB Time limit exceeded (wall clock)
13 Execution timed out 57 ms 17236 KB Time limit exceeded (wall clock)
14 Execution timed out 66 ms 17032 KB Time limit exceeded (wall clock)
15 Execution timed out 52 ms 21532 KB Time limit exceeded (wall clock)
16 Execution timed out 53 ms 26768 KB Time limit exceeded (wall clock)
17 Execution timed out 55 ms 25612 KB Time limit exceeded (wall clock)