oj.uz

Submission #524332

# Submission time Handle Problem Language Result Execution time Memory
524332 2022-02-09T04:25:04 Z keertan Regions (IOI09_regions) C++17
45 / 100
 4037 ms 102004 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[r][r1]<<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 23368 KB Output is correct
2 Correct 13 ms 23368 KB Output is correct
3 Correct 13 ms 23368 KB Output is correct
4 Correct 16 ms 23368 KB Output is correct
5 Correct 21 ms 23432 KB Output is correct
6 Correct 19 ms 23496 KB Output is correct
7 Correct 38 ms 23496 KB Output is correct
8 Correct 38 ms 23560 KB Output is correct
9 Correct 33 ms 24008 KB Output is correct
10 Correct 86 ms 23984 KB Output is correct
11 Correct 112 ms 24264 KB Output is correct
12 Correct 150 ms 24948 KB Output is correct
13 Correct 158 ms 24520 KB Output is correct
14 Correct 246 ms 25160 KB Output is correct
15 Correct 257 ms 28232 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1631 ms 29608 KB Output isn't correct
2 Incorrect 1572 ms 28292 KB Output isn't correct
3 Incorrect 2231 ms 31872 KB Output isn't correct
4 Correct 241 ms 25416 KB Output is correct
5 Correct 284 ms 27580 KB Output is correct
6 Correct 1016 ms 27076 KB Output is correct
7 Correct 1138 ms 28360 KB Output is correct
8 Correct 1076 ms 34440 KB Output is correct
9 Correct 1666 ms 34688 KB Output is correct
10 Runtime error 3536 ms 83540 KB Execution killed with signal 11
11 Runtime error 4037 ms 70708 KB Execution killed with signal 11
12 Runtime error 191 ms 76176 KB Execution killed with signal 11
13 Runtime error 121 ms 77120 KB Execution killed with signal 11
14 Runtime error 147 ms 76672 KB Execution killed with signal 11
15 Runtime error 114 ms 86996 KB Execution killed with signal 11
16 Runtime error 131 ms 102004 KB Execution killed with signal 11
17 Runtime error 117 ms 98284 KB Execution killed with signal 11