oj.uz

Submission #602341

# Submission time Handle Problem Language Result Execution time Memory
602341 2022-07-22T22:55:05 Z Quan2003 Regions (IOI09_regions) C++17
55 / 100
 4432 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=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[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 5 ms 6096 KB Output is correct
4 Correct 7 ms 6096 KB Output is correct
5 Correct 8 ms 6224 KB Output is correct
6 Correct 23 ms 6224 KB Output is correct
7 Correct 28 ms 6224 KB Output is correct
8 Correct 30 ms 6352 KB Output is correct
9 Correct 63 ms 6992 KB Output is correct
10 Correct 93 ms 7188 KB Output is correct
11 Correct 124 ms 7516 KB Output is correct
12 Correct 129 ms 8328 KB Output is correct
13 Correct 227 ms 8144 KB Output is correct
14 Correct 245 ms 9048 KB Output is correct
15 Correct 313 ms 12404 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1815 ms 13496 KB Output isn't correct
2 Incorrect 2191 ms 12548 KB Output isn't correct
3 Incorrect 2836 ms 15992 KB Output isn't correct
4 Correct 265 ms 8912 KB Output is correct
5 Correct 379 ms 10992 KB Output is correct
6 Correct 1169 ms 10768 KB Output is correct
7 Correct 1675 ms 12484 KB Output is correct
8 Correct 1193 ms 19012 KB Output is correct
9 Correct 1869 ms 21492 KB Output is correct
10 Correct 4261 ms 26856 KB Output is correct
11 Correct 4432 ms 22456 KB Output is correct
12 Incorrect 1472 ms 22992 KB Output isn't correct
13 Incorrect 2100 ms 23500 KB Output isn't correct
14 Incorrect 2631 ms 26924 KB Output isn't correct
15 Incorrect 3197 ms 28504 KB Output isn't correct
16 Incorrect 3102 ms 35356 KB Output isn't correct
17 Incorrect 3328 ms 37940 KB Output isn't correct