oj.uz

Submission #524327

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

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23368 KB Output isn't correct
2 Incorrect 13 ms 23320 KB Output isn't correct
3 Incorrect 17 ms 23368 KB Output isn't correct
4 Incorrect 16 ms 23368 KB Output isn't correct
5 Incorrect 19 ms 23368 KB Output isn't correct
6 Incorrect 41 ms 23524 KB Output isn't correct
7 Incorrect 46 ms 23504 KB Output isn't correct
8 Incorrect 43 ms 23548 KB Output isn't correct
9 Incorrect 87 ms 24104 KB Output isn't correct
10 Incorrect 73 ms 24236 KB Output isn't correct
11 Incorrect 164 ms 24596 KB Output isn't correct
12 Incorrect 165 ms 25236 KB Output isn't correct
13 Incorrect 209 ms 24860 KB Output isn't correct
14 Incorrect 361 ms 25668 KB Output isn't correct
15 Incorrect 377 ms 28952 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1922 ms 30616 KB Output isn't correct
2 Incorrect 1822 ms 29964 KB Output isn't correct
3 Incorrect 3164 ms 33160 KB Output isn't correct
4 Incorrect 273 ms 25948 KB Output isn't correct
5 Incorrect 379 ms 28180 KB Output isn't correct
6 Incorrect 797 ms 45996 KB Output isn't correct
7 Incorrect 1249 ms 50408 KB Output isn't correct
8 Incorrect 1718 ms 77792 KB Output isn't correct
9 Incorrect 3248 ms 93296 KB Output isn't correct
10 Runtime error 109 ms 90816 KB Execution killed with signal 11
11 Runtime error 127 ms 79552 KB Execution killed with signal 11
12 Runtime error 134 ms 81928 KB Execution killed with signal 11
13 Runtime error 142 ms 82816 KB Execution killed with signal 11
14 Runtime error 136 ms 82480 KB Execution killed with signal 11
15 Runtime error 146 ms 94256 KB Execution killed with signal 11
16 Runtime error 131 ms 110196 KB Execution killed with signal 11
17 Runtime error 122 ms 104472 KB Execution killed with signal 11