oj.uz

Submission #523985

# Submission time Handle Problem Language Result Execution time Memory
523985 2022-02-08T14:04:42 Z keertan Regions (IOI09_regions) C++17
45 / 100
 8000 ms 95808 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 = 2e5+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()){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 11 ms 19016 KB Output is correct
2 Correct 10 ms 19016 KB Output is correct
3 Correct 13 ms 19016 KB Output is correct
4 Correct 16 ms 19148 KB Output is correct
5 Correct 19 ms 19144 KB Output is correct
6 Correct 37 ms 19268 KB Output is correct
7 Correct 39 ms 19348 KB Output is correct
8 Correct 33 ms 19456 KB Output is correct
9 Correct 70 ms 20168 KB Output is correct
10 Correct 116 ms 20320 KB Output is correct
11 Correct 134 ms 20836 KB Output is correct
12 Correct 182 ms 21684 KB Output is correct
13 Correct 253 ms 21428 KB Output is correct
14 Correct 319 ms 22208 KB Output is correct
15 Correct 357 ms 25864 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 5926 ms 27380 KB Output is correct
2 Execution timed out 8004 ms 25916 KB Time limit exceeded
3 Execution timed out 8007 ms 31732 KB Time limit exceeded
4 Correct 273 ms 23052 KB Output is correct
5 Correct 353 ms 25900 KB Output is correct
6 Correct 1099 ms 25552 KB Output is correct
7 Correct 1152 ms 26304 KB Output is correct
8 Correct 1087 ms 36008 KB Output is correct
9 Runtime error 87 ms 61580 KB Execution killed with signal 11
10 Runtime error 90 ms 75228 KB Execution killed with signal 11
11 Runtime error 93 ms 60204 KB Execution killed with signal 11
12 Runtime error 105 ms 63444 KB Execution killed with signal 11
13 Runtime error 94 ms 64320 KB Execution killed with signal 11
14 Runtime error 98 ms 63184 KB Execution killed with signal 11
15 Runtime error 95 ms 75428 KB Execution killed with signal 11
16 Runtime error 121 ms 95808 KB Execution killed with signal 11
17 Runtime error 109 ms 89580 KB Execution killed with signal 11