oj.uz

Submission #524200

# Submission time Handle Problem Language Result Execution time Memory
524200 2022-02-08T18:48:27 Z keertan Regions (IOI09_regions) C++17
60 / 100
 3785 ms 102076 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];
unordered_map<int,int> mp[25001];
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[euler[j]][i]+=ok[j]-!!(euler[j]==i);
        }
      }
    }
  }
  for (int r,r1;q;q--){
    cin>>r>>r1;
    if (sz(col[r])>=512){cout<<mp[r1][r]<<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 12 ms 23368 KB Output is correct
2 Correct 12 ms 23368 KB Output is correct
3 Correct 12 ms 23416 KB Output is correct
4 Correct 15 ms 23368 KB Output is correct
5 Correct 20 ms 23368 KB Output is correct
6 Correct 26 ms 23448 KB Output is correct
7 Correct 29 ms 23496 KB Output is correct
8 Correct 44 ms 23496 KB Output is correct
9 Correct 58 ms 24008 KB Output is correct
10 Correct 79 ms 24008 KB Output is correct
11 Correct 122 ms 24392 KB Output is correct
12 Correct 149 ms 25088 KB Output is correct
13 Correct 176 ms 24776 KB Output is correct
14 Correct 258 ms 25488 KB Output is correct
15 Correct 326 ms 28604 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1679 ms 29812 KB Output is correct
2 Correct 1883 ms 28704 KB Output is correct
3 Correct 2584 ms 32224 KB Output is correct
4 Correct 260 ms 25616 KB Output is correct
5 Correct 320 ms 27552 KB Output is correct
6 Correct 1086 ms 27204 KB Output is correct
7 Correct 1086 ms 28556 KB Output is correct
8 Correct 1036 ms 34660 KB Output is correct
9 Correct 1609 ms 35588 KB Output is correct
10 Runtime error 3042 ms 84012 KB Execution killed with signal 11
11 Runtime error 3785 ms 71956 KB Execution killed with signal 11
12 Runtime error 127 ms 76892 KB Execution killed with signal 11
13 Runtime error 112 ms 77760 KB Execution killed with signal 11
14 Runtime error 135 ms 77696 KB Execution killed with signal 11
15 Runtime error 114 ms 88376 KB Execution killed with signal 11
16 Runtime error 119 ms 102076 KB Execution killed with signal 11
17 Runtime error 117 ms 99048 KB Execution killed with signal 11