oj.uz

답안 #591856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591856 2022-07-08T04:39:01 Z Quan2003 Regions (IOI09_regions) C++17
80 / 100
 8000 ms 36776 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<array<ll,2>>to[25001];
ll up[17][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;
}
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);
    } 
   dfs(1);
   for(int i=0;i<q;i++){
    ll u,w,res;cin>>u>>w;
    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 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 6 ms 5584 KB Output is correct
5 Correct 9 ms 5584 KB Output is correct
6 Correct 18 ms 5712 KB Output is correct
7 Correct 27 ms 5712 KB Output is correct
8 Correct 41 ms 5712 KB Output is correct
9 Correct 26 ms 6352 KB Output is correct
10 Correct 82 ms 6352 KB Output is correct
11 Correct 119 ms 6864 KB Output is correct
12 Correct 122 ms 7708 KB Output is correct
13 Correct 179 ms 7456 KB Output is correct
14 Correct 239 ms 8272 KB Output is correct
15 Correct 259 ms 12368 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8093 ms 12856 KB Time limit exceeded
2 Execution timed out 8092 ms 11704 KB Time limit exceeded
3 Execution timed out 8087 ms 15752 KB Time limit exceeded
4 Correct 278 ms 8272 KB Output is correct
5 Correct 373 ms 10696 KB Output is correct
6 Correct 1099 ms 10024 KB Output is correct
7 Correct 1407 ms 11720 KB Output is correct
8 Correct 1136 ms 19172 KB Output is correct
9 Correct 2127 ms 20276 KB Output is correct
10 Correct 4185 ms 26768 KB Output is correct
11 Correct 3504 ms 21056 KB Output is correct
12 Correct 4142 ms 21636 KB Output is correct
13 Correct 4816 ms 22404 KB Output is correct
14 Correct 5926 ms 22044 KB Output is correct
15 Correct 6791 ms 28028 KB Output is correct
16 Correct 6704 ms 36776 KB Output is correct
17 Execution timed out 8026 ms 35348 KB Time limit exceeded