oj.uz

Submission #1069820

# Submission time Handle Problem Language Result Execution time Memory
1069820 2024-08-22T09:12:46 Z doducanh Regions (IOI09_regions) C++14
100 / 100
 3456 ms 30800 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn=2e5+7;
int a[maxn];
vector<int>adj[maxn];
int innode[2*maxn];
int n,r,q;
vector<int>comp[25005];
vector<vector<int>>ans;
int in[maxn];
int out[maxn];
int cnt;
void dfs(int u,int par)
{
    in[u]=++cnt;
    comp[a[u]].push_back(in[u]);
    innode[in[u]]=u;
    for(int v:adj[u])if(v!=par){
        dfs(v,u);
    }
    out[u]=++cnt;
}
void dfs1(int u,int curr,int tmp)
{
    if(a[u]==curr)tmp++;
    ans[curr][a[u]]+=tmp;
    for(int v:adj[u]){
        dfs1(v,curr,tmp);
    }
}
int main()
{
    cin>>n>>r>>q;
    cin>>a[1];
    for(int i=2;i<=n;i++){
        int x,k;
        cin>>x>>k;
        adj[x].push_back(i);
        a[i]=k;
    }
    ans.resize(r+1);
    dfs(1,0);
    int sz=sqrt(n);
    for(int i=1;i<=r;i++){
        if(comp[i].size()>=sz){
            ans[i]=vector<int>(r+1);
            dfs1(1,i,0);
        }
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        if(comp[x].size()>=sz){
            cout<<ans[x][y]<<"\n";
        }
        else{
            int res=0;
            for(int x:comp[x]){
                res+=lower_bound(comp[y].begin(),comp[y].end(),out[innode[x]])-lower_bound(comp[y].begin(),comp[y].end(),in[innode[x]]);
            }
            cout<<res<<"\n";
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:46:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if(comp[i].size()>=sz){
      |            ~~~~~~~~~~~~~~^~~~
regions.cpp:54:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         if(comp[x].size()>=sz){
      |            ~~~~~~~~~~~~~~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 4 ms 8536 KB Output is correct
5 Correct 6 ms 8536 KB Output is correct
6 Correct 11 ms 8536 KB Output is correct
7 Correct 20 ms 8536 KB Output is correct
8 Correct 15 ms 8536 KB Output is correct
9 Correct 37 ms 9048 KB Output is correct
10 Correct 55 ms 9048 KB Output is correct
11 Correct 87 ms 9304 KB Output is correct
12 Correct 94 ms 9816 KB Output is correct
13 Correct 129 ms 9304 KB Output is correct
14 Correct 182 ms 9816 KB Output is correct
15 Correct 219 ms 12376 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1476 ms 12500 KB Output is correct
2 Correct 1698 ms 11088 KB Output is correct
3 Correct 2382 ms 13912 KB Output is correct
4 Correct 194 ms 10072 KB Output is correct
5 Correct 250 ms 11608 KB Output is correct
6 Correct 396 ms 12660 KB Output is correct
7 Correct 947 ms 13888 KB Output is correct
8 Correct 792 ms 20420 KB Output is correct
9 Correct 1829 ms 16104 KB Output is correct
10 Correct 2576 ms 30800 KB Output is correct
11 Correct 3456 ms 15440 KB Output is correct
12 Correct 1251 ms 17192 KB Output is correct
13 Correct 1764 ms 17236 KB Output is correct
14 Correct 1972 ms 18804 KB Output is correct
15 Correct 2910 ms 21504 KB Output is correct
16 Correct 2653 ms 26960 KB Output is correct
17 Correct 2488 ms 27344 KB Output is correct