oj.uz

Submission #733472

# Submission time Handle Problem Language Result Execution time Memory
733472 2023-04-30T21:31:42 Z MarwenElarbi Regions (IOI09_regions) C++14
60 / 100
 3081 ms 101988 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 12 ms 23376 KB Output is correct
2 Correct 12 ms 23408 KB Output is correct
3 Correct 14 ms 23384 KB Output is correct
4 Correct 16 ms 23388 KB Output is correct
5 Correct 19 ms 23376 KB Output is correct
6 Correct 26 ms 23504 KB Output is correct
7 Correct 41 ms 23504 KB Output is correct
8 Correct 50 ms 23476 KB Output is correct
9 Correct 60 ms 23992 KB Output is correct
10 Correct 106 ms 24048 KB Output is correct
11 Correct 127 ms 24344 KB Output is correct
12 Correct 140 ms 24912 KB Output is correct
13 Correct 176 ms 24528 KB Output is correct
14 Correct 254 ms 25168 KB Output is correct
15 Correct 311 ms 28256 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1670 ms 29628 KB Output is correct
2 Correct 1565 ms 28304 KB Output is correct
3 Correct 2254 ms 31880 KB Output is correct
4 Correct 251 ms 25392 KB Output is correct
5 Correct 355 ms 27592 KB Output is correct
6 Correct 1070 ms 27216 KB Output is correct
7 Correct 1137 ms 28344 KB Output is correct
8 Correct 1059 ms 34376 KB Output is correct
9 Correct 1798 ms 34632 KB Output is correct
10 Runtime error 3081 ms 83564 KB Execution killed with signal 11
11 Runtime error 3072 ms 70708 KB Execution killed with signal 11
12 Runtime error 120 ms 76148 KB Execution killed with signal 11
13 Runtime error 125 ms 77188 KB Execution killed with signal 11
14 Runtime error 126 ms 76748 KB Execution killed with signal 11
15 Runtime error 111 ms 86980 KB Execution killed with signal 11
16 Runtime error 125 ms 101988 KB Execution killed with signal 11
17 Runtime error 115 ms 98256 KB Execution killed with signal 11