oj.uz

답안 #591853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591853 2022-07-08T04:19:21 Z Quan2003 Regions (IOI09_regions) C++17
75 / 100
 8000 ms 31760 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int sz=2e5+1;
ll timer=1;
int n,q,m,k,r;
ll st[sz],en[sz];
ll a[sz];
vector<ll>col[25001];
vector<ll>to[25001];
ll up[17][sz];
ll par[sz];
vector<ll>adj[sz];
const int mod=1e9+7;
void dfs(int u){
    col[a[u]].push_back(timer);
    st[u]=timer++;
    for(auto v:adj[u]){
        if(v==par[u]) continue;
        dfs(v);
    } en[u]=timer-1;
}
int main(){
   cin>>n>>r>>q; 
   cin>>a[1];
   to[a[1]].push_back(1);
   for(int i=2;i<=n;i++){
       cin>>par[i]>>a[i];
       adj[par[i]].push_back(i);
       to[a[i]].push_back(i);
    } dfs(1);
      for(int i=0;i<q;i++){
         ll u,w,res;cin>>u>>w;
         const auto &v=col[w];res=0;
         for(auto p:to[u]){
           int x=upper_bound(v.begin(),v.end(),en[p])-lower_bound(v.begin(),v.end(),st[p]);
           res+=x;
          } cout<<res<<endl;
      }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 4 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 10 ms 6224 KB Output is correct
6 Correct 18 ms 6224 KB Output is correct
7 Correct 28 ms 6224 KB Output is correct
8 Correct 32 ms 6352 KB Output is correct
9 Correct 28 ms 6864 KB Output is correct
10 Correct 97 ms 7120 KB Output is correct
11 Correct 130 ms 7504 KB Output is correct
12 Correct 158 ms 8144 KB Output is correct
13 Correct 188 ms 7956 KB Output is correct
14 Correct 308 ms 8816 KB Output is correct
15 Correct 296 ms 11604 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8074 ms 12960 KB Time limit exceeded
2 Execution timed out 8044 ms 12100 KB Time limit exceeded
3 Execution timed out 8093 ms 15168 KB Time limit exceeded
4 Correct 277 ms 8776 KB Output is correct
5 Correct 403 ms 10480 KB Output is correct
6 Correct 1454 ms 10508 KB Output is correct
7 Correct 1877 ms 12232 KB Output is correct
8 Correct 1354 ms 17872 KB Output is correct
9 Correct 2420 ms 20328 KB Output is correct
10 Correct 4338 ms 25264 KB Output is correct
11 Correct 5367 ms 21656 KB Output is correct
12 Correct 5546 ms 22320 KB Output is correct
13 Correct 5818 ms 22604 KB Output is correct
14 Correct 7903 ms 22888 KB Output is correct
15 Execution timed out 8061 ms 26868 KB Time limit exceeded
16 Correct 6986 ms 31760 KB Output is correct
17 Execution timed out 8031 ms 31076 KB Time limit exceeded