oj.uz

Submission #524184

# Submission time Handle Problem Language Result Execution time Memory
524184 2022-02-08T18:27:33 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2104 ms 95696 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=(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]){
    ans+=upper_bound(all(ctin[chld]),tout[it])-ctin[chld].begin();
    ans-=upper_bound(all(ctin[chld]),tin[it])-ctin[chld].begin();
  }
  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])>=512){
      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 (sz(col[r])>=512){cout<<mp[{r,r1}]<<endl;continue;}
    else if (sz(col[r])<sz(col[r1])){
      cout<<parent(r,r1)<<endl;
    }
    else{
      cout<<child(r,r1)<<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 13 ms 21960 KB Output is correct
2 Correct 12 ms 21960 KB Output is correct
3 Correct 12 ms 21960 KB Output is correct
4 Correct 15 ms 21960 KB Output is correct
5 Correct 17 ms 22088 KB Output is correct
6 Correct 29 ms 22048 KB Output is correct
7 Correct 40 ms 22056 KB Output is correct
8 Correct 43 ms 22216 KB Output is correct
9 Correct 64 ms 22600 KB Output is correct
10 Correct 86 ms 22728 KB Output is correct
11 Correct 131 ms 23112 KB Output is correct
12 Correct 142 ms 23624 KB Output is correct
13 Correct 100 ms 23356 KB Output is correct
14 Correct 219 ms 24180 KB Output is correct
15 Correct 310 ms 27244 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1720 ms 28468 KB Output is correct
2 Correct 1627 ms 27328 KB Output is correct
3 Correct 2104 ms 30816 KB Output is correct
4 Correct 234 ms 24244 KB Output is correct
5 Correct 354 ms 26184 KB Output is correct
6 Correct 930 ms 25812 KB Output is correct
7 Correct 1014 ms 27200 KB Output is correct
8 Correct 884 ms 33280 KB Output is correct
9 Correct 1674 ms 34212 KB Output is correct
10 Runtime error 97 ms 80808 KB Execution killed with signal 11
11 Runtime error 108 ms 66752 KB Execution killed with signal 11
12 Runtime error 116 ms 70996 KB Execution killed with signal 11
13 Runtime error 115 ms 71864 KB Execution killed with signal 11
14 Runtime error 118 ms 70432 KB Execution killed with signal 11
15 Runtime error 107 ms 81088 KB Execution killed with signal 11
16 Runtime error 127 ms 95696 KB Execution killed with signal 11
17 Runtime error 116 ms 91960 KB Execution killed with signal 11