oj.uz

답안 #591852

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591852 2022-07-08T04:12:13 Z Quan2003 Regions (IOI09_regions) C++17
70 / 100
 8000 ms 30216 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 d[sz];
ll st[sz],en[sz];
ll ans[sz];
ll a[sz];
vector<ll>col[25001];
vector<ll>to[25001];
ll up[17][sz];
ll dp[sz];
vector<ll>adj[sz];
const int mod=1e9+7;
void dfs(int u,int p){
    col[a[u]].push_back(timer);
    st[u]=timer++;
    for(auto v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
    } 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++){
       ll u;cin>>u>>a[i];
       adj[u].push_back(i);
       to[a[i]].push_back(i);
    } dfs(1,0);
      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 5 ms 6096 KB Output is correct
2 Correct 4 ms 6108 KB Output is correct
3 Correct 7 ms 6096 KB Output is correct
4 Correct 9 ms 6096 KB Output is correct
5 Correct 12 ms 6224 KB Output is correct
6 Correct 21 ms 6224 KB Output is correct
7 Correct 28 ms 6224 KB Output is correct
8 Correct 37 ms 6352 KB Output is correct
9 Correct 62 ms 6864 KB Output is correct
10 Correct 107 ms 6864 KB Output is correct
11 Correct 129 ms 7272 KB Output is correct
12 Correct 184 ms 7980 KB Output is correct
13 Correct 198 ms 7888 KB Output is correct
14 Correct 338 ms 8624 KB Output is correct
15 Correct 220 ms 11256 KB Output is correct

Subtask #2
55.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8082 ms 12404 KB Time limit exceeded
2 Execution timed out 8093 ms 11588 KB Time limit exceeded
3 Execution timed out 8085 ms 14536 KB Time limit exceeded
4 Correct 286 ms 8644 KB Output is correct
5 Correct 379 ms 10180 KB Output is correct
6 Correct 1306 ms 10124 KB Output is correct
7 Correct 1911 ms 11680 KB Output is correct
8 Correct 1276 ms 17080 KB Output is correct
9 Correct 2337 ms 19272 KB Output is correct
10 Correct 4540 ms 24000 KB Output is correct
11 Correct 4847 ms 20108 KB Output is correct
12 Correct 5424 ms 20852 KB Output is correct
13 Correct 5884 ms 21124 KB Output is correct
14 Execution timed out 8071 ms 21352 KB Time limit exceeded
15 Execution timed out 8045 ms 25300 KB Time limit exceeded
16 Correct 7267 ms 30216 KB Output is correct
17 Execution timed out 8026 ms 29652 KB Time limit exceeded