oj.uz

Submission #524330

# Submission time Handle Problem Language Result Execution time Memory
524330 2022-02-09T04:22:19 Z keertan Regions (IOI09_regions) C++17
60 / 100
 3587 ms 101944 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;
  vector<int>f(r+1);
  cin>>c[1];
  f[c[1]]++;
  for (int i=2,x,p;i<=n;i++){
    cin>>p>>x;
    c[i]=x;
    f[x]++;
    adj[p].push_back(i);
  }
  for (int i=0;i<=r;i++){
    ctin[i].reserve(f[i]+2);
    ctout[i].reserve(f[i]+2);
    col[i].reserve(f[i]+2);
  }
  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 13 ms 23368 KB Output is correct
2 Correct 13 ms 23368 KB Output is correct
3 Correct 15 ms 23352 KB Output is correct
4 Correct 16 ms 23412 KB Output is correct
5 Correct 24 ms 23372 KB Output is correct
6 Correct 36 ms 23496 KB Output is correct
7 Correct 35 ms 23496 KB Output is correct
8 Correct 50 ms 23496 KB Output is correct
9 Correct 51 ms 24008 KB Output is correct
10 Correct 79 ms 24008 KB Output is correct
11 Correct 100 ms 24264 KB Output is correct
12 Correct 152 ms 24888 KB Output is correct
13 Correct 154 ms 24504 KB Output is correct
14 Correct 222 ms 25136 KB Output is correct
15 Correct 280 ms 28204 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1630 ms 29556 KB Output is correct
2 Correct 1823 ms 28336 KB Output is correct
3 Correct 2446 ms 31924 KB Output is correct
4 Correct 211 ms 25416 KB Output is correct
5 Correct 330 ms 27588 KB Output is correct
6 Correct 884 ms 27068 KB Output is correct
7 Correct 1220 ms 28356 KB Output is correct
8 Correct 829 ms 34368 KB Output is correct
9 Correct 1606 ms 34668 KB Output is correct
10 Runtime error 3337 ms 83532 KB Execution killed with signal 11
11 Runtime error 3587 ms 70708 KB Execution killed with signal 11
12 Runtime error 116 ms 76236 KB Execution killed with signal 11
13 Runtime error 107 ms 77132 KB Execution killed with signal 11
14 Runtime error 125 ms 76672 KB Execution killed with signal 11
15 Runtime error 109 ms 87072 KB Execution killed with signal 11
16 Runtime error 121 ms 101944 KB Execution killed with signal 11
17 Runtime error 112 ms 98256 KB Execution killed with signal 11