oj.uz

Submission #602338

# Submission time Handle Problem Language Result Execution time Memory
602338 2022-07-22T22:46:57 Z Quan2003 Regions (IOI09_regions) C++17
45 / 100
 4110 ms 42116 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=1;
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[500][25001];
ll up[17][sz];
ll dp[sz];
ll par[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]){
        if(v==par[u]) continue;
        dfs(v);
    } en[u]=timer-1;
}
void dfs1(int u,int tar,int curr){
    if(a[u]==tar) curr++;
    ans[dp[tar]][a[u]]+=curr;
    for(auto v:adj[u]) dfs1(v,tar,curr);
}
int main(){
   cin>>n>>r>>q; 
   cin>>a[1];
   for(int i=2;i<=n;i++){
       cin>>par[i]>>a[i];
       adj[par[i]].push_back(i);
       cmp[a[i]].push_back(i);
    } 
   dfs(1);
   for(int i=1;i<=r;i++){
       if(cmp[i].size()<500) 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]][a[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 6124 KB Output is correct
4 Correct 7 ms 6096 KB Output is correct
5 Correct 11 ms 6224 KB Output is correct
6 Correct 21 ms 6224 KB Output is correct
7 Correct 33 ms 6352 KB Output is correct
8 Correct 30 ms 6352 KB Output is correct
9 Correct 62 ms 7100 KB Output is correct
10 Correct 75 ms 7128 KB Output is correct
11 Correct 120 ms 7632 KB Output is correct
12 Correct 161 ms 8492 KB Output is correct
13 Correct 184 ms 8400 KB Output is correct
14 Correct 308 ms 9248 KB Output is correct
15 Correct 211 ms 13392 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1644 ms 14328 KB Output isn't correct
2 Incorrect 1919 ms 13212 KB Output isn't correct
3 Incorrect 2608 ms 17256 KB Output isn't correct
4 Correct 299 ms 9160 KB Output is correct
5 Correct 388 ms 11660 KB Output is correct
6 Incorrect 1065 ms 12392 KB Output isn't correct
7 Correct 1685 ms 13100 KB Output is correct
8 Incorrect 1181 ms 21208 KB Output isn't correct
9 Correct 2011 ms 22968 KB Output is correct
10 Correct 4034 ms 29512 KB Output is correct
11 Correct 4110 ms 24064 KB Output is correct
12 Incorrect 1547 ms 24532 KB Output isn't correct
13 Incorrect 2208 ms 25288 KB Output isn't correct
14 Incorrect 2267 ms 28620 KB Output isn't correct
15 Incorrect 2875 ms 31228 KB Output isn't correct
16 Incorrect 2810 ms 39884 KB Output isn't correct
17 Incorrect 2562 ms 42116 KB Output isn't correct