oj.uz

Submission #733471

# Submission time Handle Problem Language Result Execution time Memory
733471 2023-04-30T21:30:14 Z MarwenElarbi Regions (IOI09_regions) C++14
60 / 100
 3376 ms 101992 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 23376 KB Output is correct
2 Correct 12 ms 23376 KB Output is correct
3 Correct 13 ms 23376 KB Output is correct
4 Correct 14 ms 23376 KB Output is correct
5 Correct 18 ms 23376 KB Output is correct
6 Correct 26 ms 23504 KB Output is correct
7 Correct 35 ms 23512 KB Output is correct
8 Correct 40 ms 23504 KB Output is correct
9 Correct 62 ms 24016 KB Output is correct
10 Correct 98 ms 24016 KB Output is correct
11 Correct 99 ms 24360 KB Output is correct
12 Correct 148 ms 24912 KB Output is correct
13 Correct 163 ms 24540 KB Output is correct
14 Correct 256 ms 25076 KB Output is correct
15 Correct 270 ms 28240 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1491 ms 29616 KB Output is correct
2 Correct 1640 ms 28412 KB Output is correct
3 Correct 2202 ms 31976 KB Output is correct
4 Correct 240 ms 25424 KB Output is correct
5 Correct 366 ms 27660 KB Output is correct
6 Correct 861 ms 27136 KB Output is correct
7 Correct 1219 ms 28340 KB Output is correct
8 Correct 1061 ms 34376 KB Output is correct
9 Correct 1894 ms 34632 KB Output is correct
10 Runtime error 3376 ms 83480 KB Execution killed with signal 11
11 Runtime error 3273 ms 70724 KB Execution killed with signal 11
12 Runtime error 128 ms 76272 KB Execution killed with signal 11
13 Runtime error 118 ms 77064 KB Execution killed with signal 11
14 Runtime error 133 ms 76728 KB Execution killed with signal 11
15 Runtime error 117 ms 87072 KB Execution killed with signal 11
16 Runtime error 120 ms 101992 KB Execution killed with signal 11
17 Runtime error 118 ms 98328 KB Execution killed with signal 11