oj.uz

Submission #524163

# Submission time Handle Problem Language Result Execution time Memory
524163 2022-02-08T18:09:59 Z keertan Regions (IOI09_regions) C++17
1 / 100
 2626 ms 98804 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 int 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[25001];
map<pair<int,int>,int> mp;
int euler[N];
void dfs(int u){
  tin[u]=tmr;
  euler[tmr]=c[u];
  //cerr<<u<< " "<<c[u]<<"\n";
  ctin[c[u]].push_back(tmr++);
  col[c[u]].push_back(u);
  for (const int&  it:adj[u]){
    dfs(it);
  }
  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=32-__builtin_clz(sz(ctin[p]));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=32-__builtin_clz(sz(ctin[chld]));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);
  for (int i=1;i<=r;i++){
    if (sz(col[i])>=300){
      vector<int> ok(tmr+1);
      for (const int& it:col[i]){
        ok[tin[it]]++;
        ok[tout[it]]--;
      }
      for (int j=1;j<tmr;j++){
        ok[j]+=ok[j-1];
        if (euler[j]){
          mp[{i,euler[j]}]+=ok[j]-!!(euler[j]==i);
        }
      }
    }
  }
  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
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21960 KB Output is correct
2 Incorrect 12 ms 21960 KB Output isn't correct
3 Incorrect 13 ms 22052 KB Output isn't correct
4 Incorrect 14 ms 22080 KB Output isn't correct
5 Incorrect 22 ms 22116 KB Output isn't correct
6 Incorrect 22 ms 22336 KB Output isn't correct
7 Incorrect 39 ms 22300 KB Output isn't correct
8 Incorrect 41 ms 22376 KB Output isn't correct
9 Incorrect 59 ms 22976 KB Output isn't correct
10 Incorrect 77 ms 23136 KB Output isn't correct
11 Incorrect 109 ms 23680 KB Output isn't correct
12 Incorrect 123 ms 24380 KB Output isn't correct
13 Incorrect 179 ms 24156 KB Output isn't correct
14 Incorrect 169 ms 24792 KB Output isn't correct
15 Incorrect 133 ms 28104 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 924 ms 29548 KB Output isn't correct
2 Incorrect 990 ms 28340 KB Output isn't correct
3 Incorrect 1283 ms 34068 KB Output isn't correct
4 Incorrect 246 ms 26004 KB Output isn't correct
5 Incorrect 315 ms 28272 KB Output isn't correct
6 Incorrect 980 ms 50712 KB Output isn't correct
7 Incorrect 1339 ms 59876 KB Output isn't correct
8 Incorrect 2099 ms 98804 KB Output isn't correct
9 Incorrect 2626 ms 84360 KB Output isn't correct
10 Runtime error 103 ms 80824 KB Execution killed with signal 11
11 Runtime error 104 ms 66712 KB Execution killed with signal 11
12 Runtime error 114 ms 70908 KB Execution killed with signal 11
13 Runtime error 104 ms 71800 KB Execution killed with signal 11
14 Runtime error 127 ms 70500 KB Execution killed with signal 11
15 Runtime error 106 ms 80960 KB Execution killed with signal 11
16 Runtime error 113 ms 95672 KB Execution killed with signal 11
17 Runtime error 115 ms 91928 KB Execution killed with signal 11