oj.uz

답안 #602339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602339 2022-07-22T22:51:19 Z Quan2003 Regions (IOI09_regions) C++17
45 / 100
 3867 ms 42104 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];
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 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++){
       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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 3 ms 6096 KB Output is correct
3 Correct 4 ms 6096 KB Output is correct
4 Correct 6 ms 6096 KB Output is correct
5 Correct 9 ms 6224 KB Output is correct
6 Correct 17 ms 6224 KB Output is correct
7 Correct 32 ms 6352 KB Output is correct
8 Correct 36 ms 6352 KB Output is correct
9 Correct 43 ms 7076 KB Output is correct
10 Correct 78 ms 7148 KB Output is correct
11 Correct 125 ms 7684 KB Output is correct
12 Correct 105 ms 8528 KB Output is correct
13 Correct 187 ms 8348 KB Output is correct
14 Correct 288 ms 9296 KB Output is correct
15 Correct 299 ms 13392 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1582 ms 14320 KB Output isn't correct
2 Incorrect 2196 ms 13216 KB Output isn't correct
3 Incorrect 2716 ms 17248 KB Output isn't correct
4 Correct 245 ms 9168 KB Output is correct
5 Correct 335 ms 11720 KB Output is correct
6 Incorrect 1030 ms 12464 KB Output isn't correct
7 Correct 1683 ms 13128 KB Output is correct
8 Incorrect 1232 ms 21180 KB Output isn't correct
9 Correct 2011 ms 22984 KB Output is correct
10 Correct 3710 ms 29500 KB Output is correct
11 Correct 3867 ms 24060 KB Output is correct
12 Incorrect 1497 ms 24528 KB Output isn't correct
13 Incorrect 1854 ms 25284 KB Output isn't correct
14 Incorrect 2490 ms 28624 KB Output isn't correct
15 Incorrect 3382 ms 31152 KB Output isn't correct
16 Incorrect 3086 ms 39916 KB Output isn't correct
17 Incorrect 2676 ms 42104 KB Output isn't correct