oj.uz

Submission #524201

# Submission time Handle Problem Language Result Execution time Memory
524201 2022-02-08T18:49:23 Z keertan Regions (IOI09_regions) C++17
60 / 100
 3633 ms 102080 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 23368 KB Output is correct
4 Correct 17 ms 23368 KB Output is correct
5 Correct 19 ms 23348 KB Output is correct
6 Correct 32 ms 23496 KB Output is correct
7 Correct 40 ms 23496 KB Output is correct
8 Correct 46 ms 23460 KB Output is correct
9 Correct 63 ms 24008 KB Output is correct
10 Correct 91 ms 24008 KB Output is correct
11 Correct 132 ms 24392 KB Output is correct
12 Correct 151 ms 25032 KB Output is correct
13 Correct 170 ms 24692 KB Output is correct
14 Correct 261 ms 25408 KB Output is correct
15 Correct 287 ms 28536 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1361 ms 29760 KB Output is correct
2 Correct 1527 ms 28596 KB Output is correct
3 Correct 2048 ms 32124 KB Output is correct
4 Correct 243 ms 25588 KB Output is correct
5 Correct 417 ms 27500 KB Output is correct
6 Correct 1095 ms 27072 KB Output is correct
7 Correct 1208 ms 28612 KB Output is correct
8 Correct 970 ms 34624 KB Output is correct
9 Correct 1721 ms 35432 KB Output is correct
10 Runtime error 3397 ms 83972 KB Execution killed with signal 11
11 Runtime error 3633 ms 71924 KB Execution killed with signal 11
12 Runtime error 199 ms 76984 KB Execution killed with signal 11
13 Runtime error 184 ms 77620 KB Execution killed with signal 11
14 Runtime error 202 ms 77744 KB Execution killed with signal 11
15 Runtime error 184 ms 88316 KB Execution killed with signal 11
16 Runtime error 186 ms 102080 KB Execution killed with signal 11
17 Runtime error 198 ms 99008 KB Execution killed with signal 11