oj.uz

Submission #524335

# Submission time Handle Problem Language Result Execution time Memory
524335 2022-02-09T04:26:41 Z keertan Regions (IOI09_regions) C++17
15 / 100
 3008 ms 131076 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])<=500){
      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 23368 KB Output is correct
2 Correct 12 ms 23312 KB Output is correct
3 Correct 12 ms 23368 KB Output is correct
4 Correct 13 ms 23368 KB Output is correct
5 Correct 18 ms 23496 KB Output is correct
6 Correct 32 ms 25848 KB Output is correct
7 Correct 45 ms 24520 KB Output is correct
8 Correct 53 ms 25160 KB Output is correct
9 Correct 111 ms 28068 KB Output is correct
10 Correct 199 ms 31452 KB Output is correct
11 Correct 241 ms 27840 KB Output is correct
12 Correct 379 ms 33280 KB Output is correct
13 Correct 402 ms 29764 KB Output is correct
14 Correct 387 ms 27036 KB Output is correct
15 Correct 511 ms 30836 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1900 ms 31076 KB Output isn't correct
2 Incorrect 2203 ms 30008 KB Output isn't correct
3 Incorrect 3008 ms 34288 KB Output isn't correct
4 Runtime error 915 ms 131076 KB Execution killed with signal 9
5 Runtime error 1263 ms 131076 KB Execution killed with signal 9
6 Runtime error 1008 ms 131076 KB Execution killed with signal 9
7 Runtime error 1030 ms 131076 KB Execution killed with signal 9
8 Runtime error 1082 ms 131076 KB Execution killed with signal 9
9 Runtime error 1354 ms 131076 KB Execution killed with signal 9
10 Runtime error 119 ms 86212 KB Execution killed with signal 11
11 Runtime error 132 ms 73952 KB Execution killed with signal 11
12 Runtime error 116 ms 76196 KB Execution killed with signal 11
13 Runtime error 114 ms 77060 KB Execution killed with signal 11
14 Runtime error 119 ms 76644 KB Execution killed with signal 11
15 Runtime error 121 ms 87064 KB Execution killed with signal 11
16 Runtime error 138 ms 101952 KB Execution killed with signal 11
17 Runtime error 110 ms 98248 KB Execution killed with signal 11