oj.uz

Submission #835105

# Submission time Handle Problem Language Result Execution time Memory
835105 2023-08-23T08:24:40 Z Denkata Regions (IOI09_regions) C++17
35 / 100
 4596 ms 26824 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]<<endl;
        else
            cout<<calc()<<endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 3 ms 6096 KB Output is correct
3 Correct 4 ms 6256 KB Output is correct
4 Correct 10 ms 6224 KB Output is correct
5 Correct 8 ms 6224 KB Output is correct
6 Correct 20 ms 6224 KB Output is correct
7 Correct 22 ms 6224 KB Output is correct
8 Correct 34 ms 6372 KB Output is correct
9 Correct 47 ms 6736 KB Output is correct
10 Correct 61 ms 6736 KB Output is correct
11 Correct 113 ms 6992 KB Output is correct
12 Correct 96 ms 7504 KB Output is correct
13 Correct 172 ms 7248 KB Output is correct
14 Correct 282 ms 7760 KB Output is correct
15 Correct 214 ms 10284 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 19 ms 10832 KB Time limit exceeded (wall clock)
2 Execution timed out 21 ms 9680 KB Time limit exceeded (wall clock)
3 Execution timed out 21 ms 12624 KB Time limit exceeded (wall clock)
4 Correct 240 ms 8016 KB Output is correct
5 Correct 338 ms 9424 KB Output is correct
6 Execution timed out 23 ms 9188 KB Time limit exceeded (wall clock)
7 Execution timed out 22 ms 10320 KB Time limit exceeded (wall clock)
8 Execution timed out 37 ms 15176 KB Time limit exceeded (wall clock)
9 Correct 2061 ms 15696 KB Output is correct
10 Execution timed out 42 ms 20748 KB Time limit exceeded (wall clock)
11 Correct 4596 ms 15616 KB Output is correct
12 Execution timed out 56 ms 17180 KB Time limit exceeded (wall clock)
13 Execution timed out 50 ms 17212 KB Time limit exceeded (wall clock)
14 Execution timed out 79 ms 17140 KB Time limit exceeded (wall clock)
15 Execution timed out 50 ms 21448 KB Time limit exceeded (wall clock)
16 Execution timed out 55 ms 26824 KB Time limit exceeded (wall clock)
17 Execution timed out 64 ms 25544 KB Time limit exceeded (wall clock)