oj.uz

Submission #523990

# Submission time Handle Problem Language Result Execution time Memory
523990 2022-02-08T14:07:51 Z keertan Regions (IOI09_regions) C++17
0 / 100
 109 ms 56200 KB 
#include <bits/stdc++.h>

using namespace std;
//#define int  int64_t
#define rep(Begin,End) for (Begin=0;Begin<(End);Begin++)
#define all(x) x.begin(), x.end()
#define all1(x) x.rbegin(), x.rend()
#define sz(x) (int32_t)(x.size())
const int64_t N = 3e5+4, mod =998244353;
const int64_t N1=1e18;
const double eps=1e-6,cmp=1e-3;
int tin[N],tout[N],c[N];
int tmr=1;
vector<int> adj[N];
vector<int> ctin[N],ctout[N],col[N];
void dfs(int u,int v){
  tin[u]=tmr;
  ctin[c[u]].push_back(tmr++);
  col[c[u]].push_back(u);
  for (const int&  it:adj[u]){
    if (it==v){continue;}
    dfs(it,u);
  }
  tout[u]=tmr;
  ctout[c[u]].push_back(tout[u]);
}
int child(int p,int chld){
  int ans=0;
  //cerr<<"chld";
  for (const int& it:col[chld]){
    //cerr<<it<<" ";
    int cur=0,cur1=0;
    for (int lg=(1ll<<18);lg;lg>>=1){
      if (sz(ctin[p])>=cur+lg && ctin[p][cur+lg-1]<tin[it]){
        cur+=lg;
      }
      if (sz(ctout[p])>=cur1+lg && ctout[p][cur1+lg-1]<=tin[it]){
        cur1+=lg;
      }
    }
    ans+=cur-cur1;
  }
  return ans;
}
int parent(int p,int chld){
  int ans=0;
  for (const int& it:col[p]){
    int cur=0,cur1=0;
    for (int lg=(1ll<<18);lg;lg>>=1){
      if (sz(ctin[chld])>=cur+lg && ctin[chld][cur+lg-1]<=tin[it]){
        cur+=lg;
      }
      if (sz(ctin[chld])>=cur1+lg && ctin[chld][cur1+lg-1]<=tout[it]){
        cur1+=lg;
      }
    }
      ans+=cur1-cur;
  }
  return ans;
}
void solve(){
  int n,r,q;
  cin>>n>>r>>q;
  cin>>c[1];
  for (int i=2,x,p;i<=n;i++){
    cin>>p>>x;
    c[i]=x;
    adj[p].push_back(i);
  }
  dfs(1,1);
  map<pair<int,int>,int> mp;
  for (int r,r1;q;q--){
    cin>>r>>r1;
    if (mp.find({r,r1})!=mp.end()){cout<<mp[{r,r1}]<<"\n";continue;}
    int ans=0;
    if (sz(col[r])<sz(col[r1])){
      ans=parent(r,r1);
    }
    else{
     // cerr<<"fck\n";
      ans=child(r,r1);
    }
    mp[{r,r1}]=ans;
    cout<<ans<<"\n";
  }
}
int32_t main(){
  ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
  int tq = 1;
  //cin>>tq;
  for (;tq;tq--){solve();}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 12 ms 28488 KB Time limit exceeded (wall clock)
2 Execution timed out 13 ms 28488 KB Time limit exceeded (wall clock)
3 Execution timed out 13 ms 28488 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 28488 KB Time limit exceeded (wall clock)
5 Execution timed out 17 ms 28488 KB Time limit exceeded (wall clock)
6 Execution timed out 13 ms 28616 KB Time limit exceeded (wall clock)
7 Execution timed out 13 ms 28616 KB Time limit exceeded (wall clock)
8 Execution timed out 14 ms 28616 KB Time limit exceeded (wall clock)
9 Execution timed out 15 ms 29204 KB Time limit exceeded (wall clock)
10 Execution timed out 16 ms 29000 KB Time limit exceeded (wall clock)
11 Execution timed out 17 ms 29384 KB Time limit exceeded (wall clock)
12 Execution timed out 19 ms 30024 KB Time limit exceeded (wall clock)
13 Execution timed out 20 ms 29640 KB Time limit exceeded (wall clock)
14 Execution timed out 21 ms 30276 KB Time limit exceeded (wall clock)
15 Execution timed out 25 ms 34148 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 33 ms 33980 KB Time limit exceeded (wall clock)
2 Execution timed out 36 ms 32456 KB Time limit exceeded (wall clock)
3 Execution timed out 35 ms 36420 KB Time limit exceeded (wall clock)
4 Execution timed out 25 ms 30400 KB Time limit exceeded (wall clock)
5 Execution timed out 26 ms 32716 KB Time limit exceeded (wall clock)
6 Execution timed out 49 ms 31972 KB Time limit exceeded (wall clock)
7 Execution timed out 42 ms 33212 KB Time limit exceeded (wall clock)
8 Execution timed out 62 ms 40216 KB Time limit exceeded (wall clock)
9 Execution timed out 79 ms 39764 KB Time limit exceeded (wall clock)
10 Execution timed out 71 ms 46976 KB Time limit exceeded (wall clock)
11 Execution timed out 92 ms 39528 KB Time limit exceeded (wall clock)
12 Execution timed out 107 ms 40456 KB Time limit exceeded (wall clock)
13 Execution timed out 106 ms 41088 KB Time limit exceeded (wall clock)
14 Execution timed out 109 ms 40860 KB Time limit exceeded (wall clock)
15 Execution timed out 84 ms 47392 KB Time limit exceeded (wall clock)
16 Execution timed out 97 ms 56200 KB Time limit exceeded (wall clock)
17 Execution timed out 80 ms 54080 KB Time limit exceeded (wall clock)