oj.uz

Submission #591908

# Submission time Handle Problem Language Result Execution time Memory
591908 2022-07-08T08:16:27 Z Quan2003 Regions (IOI09_regions) C++17
13 / 100
 8000 ms 36868 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;  
    if(to[w].size()>0 and to[u].size()>0){
        int d=to[u][to[u].size()-1][1];
        int e=to[w][0][1];
        if(st[e]>=1+en[d]){
            cout<<0<<endl;
            continue;
        } 
        d=to[w][to[w].size()-1][1];
        e=to[u][0][1];
          if(st[e]>=1+en[d]){
              cout<<0<<endl;
              continue;
          }
    }
    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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5560 KB Output is correct
3 Correct 4 ms 5584 KB Output is correct
4 Incorrect 7 ms 5584 KB Output isn't correct
5 Correct 11 ms 5584 KB Output is correct
6 Correct 24 ms 5712 KB Output is correct
7 Incorrect 21 ms 5712 KB Output isn't correct
8 Correct 33 ms 5712 KB Output is correct
9 Correct 48 ms 6480 KB Output is correct
10 Correct 80 ms 6448 KB Output is correct
11 Correct 105 ms 6864 KB Output is correct
12 Correct 96 ms 7632 KB Output is correct
13 Correct 174 ms 7536 KB Output is correct
14 Correct 249 ms 8296 KB Output is correct
15 Correct 297 ms 12304 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8077 ms 12864 KB Time limit exceeded
2 Execution timed out 8025 ms 11648 KB Time limit exceeded
3 Execution timed out 8068 ms 15812 KB Time limit exceeded
4 Incorrect 286 ms 8240 KB Output isn't correct
5 Incorrect 388 ms 10704 KB Output isn't correct
6 Incorrect 1389 ms 10068 KB Output isn't correct
7 Incorrect 1620 ms 11628 KB Output isn't correct
8 Incorrect 1264 ms 19184 KB Output isn't correct
9 Incorrect 2327 ms 20268 KB Output isn't correct
10 Incorrect 4065 ms 26712 KB Output isn't correct
11 Incorrect 3558 ms 21056 KB Output isn't correct
12 Incorrect 4864 ms 21636 KB Output isn't correct
13 Incorrect 5271 ms 22396 KB Output isn't correct
14 Incorrect 6958 ms 22000 KB Output isn't correct
15 Incorrect 7283 ms 28040 KB Output isn't correct
16 Incorrect 7350 ms 36868 KB Output isn't correct
17 Execution timed out 8010 ms 35424 KB Time limit exceeded