oj.uz

Submission #524337

# Submission time Handle Problem Language Result Execution time Memory
524337 2022-02-09T04:27:42 Z keertan Regions (IOI09_regions) C++17
15 / 100
 2602 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])<=200){
      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 23368 KB Output is correct
2 Correct 13 ms 23368 KB Output is correct
3 Correct 14 ms 23368 KB Output is correct
4 Correct 16 ms 23476 KB Output is correct
5 Correct 21 ms 23424 KB Output is correct
6 Correct 42 ms 25836 KB Output is correct
7 Correct 51 ms 24520 KB Output is correct
8 Correct 58 ms 25148 KB Output is correct
9 Correct 97 ms 28112 KB Output is correct
10 Correct 179 ms 31464 KB Output is correct
11 Correct 220 ms 27916 KB Output is correct
12 Correct 415 ms 33368 KB Output is correct
13 Correct 383 ms 29732 KB Output is correct
14 Correct 380 ms 27100 KB Output is correct
15 Correct 491 ms 30780 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1625 ms 30296 KB Output isn't correct
2 Incorrect 1681 ms 28624 KB Output isn't correct
3 Incorrect 2602 ms 34292 KB Output isn't correct
4 Runtime error 900 ms 131076 KB Execution killed with signal 9
5 Runtime error 1297 ms 131076 KB Execution killed with signal 9
6 Runtime error 1063 ms 131076 KB Execution killed with signal 9
7 Runtime error 1020 ms 131076 KB Execution killed with signal 9
8 Runtime error 1062 ms 131076 KB Execution killed with signal 9
9 Runtime error 1299 ms 131076 KB Execution killed with signal 9
10 Runtime error 103 ms 86200 KB Execution killed with signal 11
11 Runtime error 123 ms 73892 KB Execution killed with signal 11
12 Runtime error 123 ms 76204 KB Execution killed with signal 11
13 Runtime error 107 ms 77140 KB Execution killed with signal 11
14 Runtime error 121 ms 76672 KB Execution killed with signal 11
15 Runtime error 111 ms 87048 KB Execution killed with signal 11
16 Runtime error 131 ms 102004 KB Execution killed with signal 11
17 Runtime error 111 ms 98300 KB Execution killed with signal 11