oj.uz

Submission #602342

# Submission time Handle Problem Language Result Execution time Memory
602342 2022-07-22T22:58:05 Z Quan2003 Regions (IOI09_regions) C++17
55 / 100
 4536 ms 37944 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]][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 6 ms 6096 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct
5 Correct 10 ms 6224 KB Output is correct
6 Correct 17 ms 6224 KB Output is correct
7 Correct 27 ms 6224 KB Output is correct
8 Correct 41 ms 6352 KB Output is correct
9 Correct 52 ms 6992 KB Output is correct
10 Correct 103 ms 7008 KB Output is correct
11 Correct 120 ms 7504 KB Output is correct
12 Correct 165 ms 8332 KB Output is correct
13 Correct 193 ms 8208 KB Output is correct
14 Correct 271 ms 9052 KB Output is correct
15 Correct 287 ms 12496 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1663 ms 13492 KB Output isn't correct
2 Incorrect 2164 ms 12556 KB Output isn't correct
3 Incorrect 2826 ms 15996 KB Output isn't correct
4 Correct 232 ms 8980 KB Output is correct
5 Correct 323 ms 11004 KB Output is correct
6 Correct 1206 ms 10656 KB Output is correct
7 Correct 1470 ms 12580 KB Output is correct
8 Correct 1334 ms 19116 KB Output is correct
9 Correct 2131 ms 21496 KB Output is correct
10 Correct 4536 ms 26828 KB Output is correct
11 Correct 4253 ms 22460 KB Output is correct
12 Incorrect 1480 ms 23108 KB Output isn't correct
13 Incorrect 2009 ms 23616 KB Output isn't correct
14 Incorrect 2880 ms 26932 KB Output isn't correct
15 Incorrect 3239 ms 28500 KB Output isn't correct
16 Incorrect 3091 ms 35360 KB Output isn't correct
17 Incorrect 3032 ms 37944 KB Output isn't correct