oj.uz

Submission #524324

# Submission time Handle Problem Language Result Execution time Memory
524324 2022-02-09T04:18:56 Z keertan Regions (IOI09_regions) C++17
0 / 100
 3078 ms 106672 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].resize(f[i]);
    ctout[i].resize(f[i]);
    col[i].resize(f[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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23368 KB Output isn't correct
2 Incorrect 13 ms 23368 KB Output isn't correct
3 Incorrect 15 ms 23312 KB Output isn't correct
4 Incorrect 17 ms 23324 KB Output isn't correct
5 Incorrect 20 ms 23368 KB Output isn't correct
6 Incorrect 29 ms 23496 KB Output isn't correct
7 Incorrect 47 ms 23472 KB Output isn't correct
8 Incorrect 46 ms 23576 KB Output isn't correct
9 Incorrect 67 ms 24068 KB Output isn't correct
10 Incorrect 95 ms 24136 KB Output isn't correct
11 Incorrect 134 ms 24592 KB Output isn't correct
12 Incorrect 166 ms 25160 KB Output isn't correct
13 Incorrect 180 ms 24812 KB Output isn't correct
14 Incorrect 276 ms 25616 KB Output isn't correct
15 Incorrect 263 ms 28944 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1944 ms 30596 KB Output isn't correct
2 Incorrect 1665 ms 29888 KB Output isn't correct
3 Incorrect 3078 ms 33060 KB Output isn't correct
4 Incorrect 274 ms 25712 KB Output isn't correct
5 Incorrect 384 ms 27836 KB Output isn't correct
6 Incorrect 777 ms 45760 KB Output isn't correct
7 Incorrect 1355 ms 50016 KB Output isn't correct
8 Incorrect 1556 ms 77780 KB Output isn't correct
9 Incorrect 2706 ms 92684 KB Output isn't correct
10 Runtime error 123 ms 90576 KB Execution killed with signal 11
11 Runtime error 144 ms 78408 KB Execution killed with signal 11
12 Runtime error 120 ms 80564 KB Execution killed with signal 11
13 Runtime error 129 ms 81476 KB Execution killed with signal 11
14 Runtime error 141 ms 80504 KB Execution killed with signal 11
15 Runtime error 131 ms 91712 KB Execution killed with signal 11
16 Runtime error 134 ms 106672 KB Execution killed with signal 11
17 Runtime error 121 ms 102528 KB Execution killed with signal 11