oj.uz

Submission #524328

# Submission time Handle Problem Language Result Execution time Memory
524328 2022-02-09T04:20:54 Z keertan Regions (IOI09_regions) C++17
0 / 100
 3132 ms 110204 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 13 ms 23368 KB Output isn't correct
2 Incorrect 12 ms 23368 KB Output isn't correct
3 Incorrect 15 ms 23376 KB Output isn't correct
4 Incorrect 21 ms 23368 KB Output isn't correct
5 Incorrect 19 ms 23400 KB Output isn't correct
6 Incorrect 26 ms 23496 KB Output isn't correct
7 Incorrect 40 ms 23496 KB Output isn't correct
8 Incorrect 28 ms 23524 KB Output isn't correct
9 Incorrect 66 ms 24124 KB Output isn't correct
10 Incorrect 81 ms 24168 KB Output isn't correct
11 Incorrect 138 ms 24596 KB Output isn't correct
12 Incorrect 150 ms 25288 KB Output isn't correct
13 Incorrect 212 ms 24904 KB Output isn't correct
14 Incorrect 334 ms 25544 KB Output isn't correct
15 Incorrect 379 ms 28964 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1798 ms 30656 KB Output isn't correct
2 Incorrect 1720 ms 29972 KB Output isn't correct
3 Incorrect 3132 ms 33076 KB Output isn't correct
4 Incorrect 243 ms 25908 KB Output isn't correct
5 Incorrect 355 ms 28104 KB Output isn't correct
6 Incorrect 733 ms 45996 KB Output isn't correct
7 Incorrect 1238 ms 50448 KB Output isn't correct
8 Incorrect 1678 ms 77840 KB Output isn't correct
9 Incorrect 2947 ms 93216 KB Output isn't correct
10 Runtime error 109 ms 90820 KB Execution killed with signal 11
11 Runtime error 145 ms 79620 KB Execution killed with signal 11
12 Runtime error 149 ms 81848 KB Execution killed with signal 11
13 Runtime error 118 ms 82720 KB Execution killed with signal 11
14 Runtime error 130 ms 82524 KB Execution killed with signal 11
15 Runtime error 134 ms 94272 KB Execution killed with signal 11
16 Runtime error 144 ms 110204 KB Execution killed with signal 11
17 Runtime error 121 ms 104512 KB Execution killed with signal 11