oj.uz

Submission #523987

# Submission time Handle Problem Language Result Execution time Memory
523987 2022-02-08T14:06:16 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2009 ms 115720 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];
int stnd[N],ennd[N];
void dfs(int u,int v){
  tin[u]=tmr;
  stnd[tmr]=u;
  //cerr<<u<< " "<<c[u]<<"\n";
  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;
  ennd[tmr++]=u;
  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;
      }
    }
    //cerr<<cur<<" "<<cur1;
    ans+=cur-cur1;
  }
  return ans;
}
int parent(int p,int chld){
  int ans=0;
  //cerr<<"gh";
  //cout<<tin[1]<<" "<<tout[1]<<"\n";
  for (const int& it:col[p]){
    //cerr<<it<<" ";
    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;
      }
    }
    // cerr<<cur<<" "<<cur1<<"\n";
      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}]<<endl;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<<endl;
  }
}
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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28488 KB Output is correct
2 Correct 16 ms 28488 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Correct 19 ms 28532 KB Output is correct
5 Correct 22 ms 28488 KB Output is correct
6 Correct 36 ms 28688 KB Output is correct
7 Correct 46 ms 28708 KB Output is correct
8 Correct 54 ms 28768 KB Output is correct
9 Correct 53 ms 29820 KB Output is correct
10 Correct 113 ms 29704 KB Output is correct
11 Correct 127 ms 30180 KB Output is correct
12 Correct 173 ms 31168 KB Output is correct
13 Correct 192 ms 30764 KB Output is correct
14 Correct 235 ms 31632 KB Output is correct
15 Correct 315 ms 35372 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 859 ms 36892 KB Output is correct
2 Correct 1222 ms 35428 KB Output is correct
3 Correct 2009 ms 41484 KB Output is correct
4 Correct 264 ms 32492 KB Output is correct
5 Correct 444 ms 35284 KB Output is correct
6 Correct 501 ms 34836 KB Output is correct
7 Correct 714 ms 35464 KB Output is correct
8 Correct 1014 ms 45448 KB Output is correct
9 Correct 1617 ms 50216 KB Output is correct
10 Runtime error 119 ms 98496 KB Execution killed with signal 11
11 Runtime error 118 ms 82300 KB Execution killed with signal 11
12 Runtime error 126 ms 86536 KB Execution killed with signal 11
13 Runtime error 113 ms 87872 KB Execution killed with signal 11
14 Runtime error 137 ms 86168 KB Execution killed with signal 11
15 Runtime error 118 ms 97820 KB Execution killed with signal 11
16 Runtime error 142 ms 115720 KB Execution killed with signal 11
17 Runtime error 123 ms 111448 KB Execution killed with signal 11