oj.uz

Submission #602344

# Submission time Handle Problem Language Result Execution time Memory
602344 2022-07-22T23:00:40 Z Quan2003 Regions (IOI09_regions) C++17
100 / 100
 4070 ms 37940 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int sz=2e5+1;
const int block=500;
ll timer=1;
ll curr=0;
int n,q,m,k,r;
ll st[sz],en[sz];
ll a[sz];
vector<array<ll,2>>to[25001];
vector<ll>cmp[25001];
ll ans[501][25001];
ll dp[sz];
vector<ll>adj[sz];
struct compare {
 bool operator()(const array<ll,2>& value,
        const int& key)
 {
  return (value[0] < key);
 }
 bool operator()(const int& key,
     const array<ll,2>& value)
 {
  return (key < value[0]);
 }
};
const int mod=1e9+7;
void dfs(int u){
    to[a[u]].push_back({timer,u});
    st[u]=timer++;
    for(auto v:adj[u]) dfs(v);
     en[u]=timer-1;
}
void dfs1(int u,int tar,int x){
    if(a[u]==tar) x++;
    ans[dp[tar]][a[u]]+=x;
    for(auto v:adj[u]) dfs1(v,tar,x);
}
int main(){
   cin>>n>>r>>q; 
   cin>>a[1];
   cmp[a[1]].push_back(1);
   for(int i=2;i<=n;i++){
       int x;cin>>x>>a[i];
       adj[x].push_back(i);
       cmp[a[i]].push_back(i);
    } 
   dfs(1);
   for(int i=1;i<=r;i++){
       if(cmp[i].size()<501) continue;
       dp[i]=++curr;
       dfs1(1,i,0);
   }
   for(int i=0;i<q;i++){
    ll u,w,res;cin>>u>>w;
    if(dp[u]>0) cout<<ans[dp[u]][w]<<endl;
    else{
    const auto &p=to[w];res=0;  
    for(auto v:to[u]){
      int x=upper_bound(p.begin(),p.end(),en[v[1]],compare())-lower_bound(p.begin(),p.end(),st[v[1]],compare());
      res+=x;
       } cout<<res<<endl;
    }
  }
}

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 5 ms 6096 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct
5 Correct 8 ms 6224 KB Output is correct
6 Correct 24 ms 6224 KB Output is correct
7 Correct 35 ms 6224 KB Output is correct
8 Correct 38 ms 6352 KB Output is correct
9 Correct 58 ms 6984 KB Output is correct
10 Correct 88 ms 6992 KB Output is correct
11 Correct 122 ms 7504 KB Output is correct
12 Correct 134 ms 8232 KB Output is correct
13 Correct 186 ms 8144 KB Output is correct
14 Correct 256 ms 9044 KB Output is correct
15 Correct 279 ms 12488 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1512 ms 13540 KB Output is correct
2 Correct 1979 ms 12552 KB Output is correct
3 Correct 2751 ms 15996 KB Output is correct
4 Correct 241 ms 9040 KB Output is correct
5 Correct 320 ms 11008 KB Output is correct
6 Correct 1250 ms 10660 KB Output is correct
7 Correct 1405 ms 12544 KB Output is correct
8 Correct 1273 ms 19052 KB Output is correct
9 Correct 2065 ms 21488 KB Output is correct
10 Correct 4070 ms 26840 KB Output is correct
11 Correct 3375 ms 22580 KB Output is correct
12 Correct 1340 ms 22988 KB Output is correct
13 Correct 1835 ms 23508 KB Output is correct
14 Correct 2526 ms 26912 KB Output is correct
15 Correct 2573 ms 28528 KB Output is correct
16 Correct 3005 ms 35460 KB Output is correct
17 Correct 2956 ms 37940 KB Output is correct