oj.uz

Submission #524167

# Submission time Handle Problem Language Result Execution time Memory
524167 2022-02-08T18:15:29 Z keertan Regions (IOI09_regions) C++17
55 / 100
 2862 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];
map<pair<int,int>,int> mp;
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]){
    //cerr<<it<<" ";
    int cur=0,cur1=0;
    for (int lg=(1ll<<18);lg;lg>>=1){
      if (sz(ctin[chld])>=cur+lg && ctin[chld][cur+lg-1]<=tin[it]){
        cur+=lg;
      }
      if (sz(ctin[chld])>=cur1+lg && ctin[chld][cur1+lg-1]<=tout[it]){
        cur1+=lg;
      }
    }
    // cerr<<cur<<" "<<cur1<<"\n";
      ans+=cur1-cur;
  }
  return ans;
}
void solve(){
  int n,r,q;
  cin>>n>>r>>q;
  cin>>c[1];
  for (int i=2,x,p;i<=n;i++){
    cin>>p>>x;
    c[i]=x;
    adj[p].push_back(i);
  }
  dfs(1);
  for (int i=1;i<=r;i++){
    if (sz(col[i])>=150){
      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[{i,euler[j]}]+=ok[j]-!!(euler[j]==i);
        }
      }
    }
  }
  for (int r,r1;q;q--){
    cin>>r>>r1;
    if (mp.find({r,r1})!=mp.end()){cout<<mp[{r,r1}]<<endl;continue;}
    int ans=0;
    if (sz(col[r])<sz(col[r1])){
      ans=parent(r,r1);
    }
    else{
     // cerr<<"fck\n";
      ans=child(r,r1);
    }
    mp[{r,r1}]=ans;
    cout<<ans<<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 21960 KB Output is correct
2 Correct 12 ms 21960 KB Output is correct
3 Correct 14 ms 21960 KB Output is correct
4 Correct 15 ms 22084 KB Output is correct
5 Correct 21 ms 22116 KB Output is correct
6 Correct 27 ms 22336 KB Output is correct
7 Correct 41 ms 22208 KB Output is correct
8 Correct 45 ms 22324 KB Output is correct
9 Correct 61 ms 22876 KB Output is correct
10 Correct 93 ms 23092 KB Output is correct
11 Correct 112 ms 23540 KB Output is correct
12 Correct 160 ms 24408 KB Output is correct
13 Correct 157 ms 24148 KB Output is correct
14 Correct 419 ms 25796 KB Output is correct
15 Correct 996 ms 30920 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1690 ms 30868 KB Output is correct
2 Correct 1557 ms 29496 KB Output is correct
3 Correct 2862 ms 34900 KB Output is correct
4 Correct 473 ms 37060 KB Output is correct
5 Correct 385 ms 28332 KB Output is correct
6 Correct 910 ms 50584 KB Output is correct
7 Correct 1496 ms 76556 KB Output is correct
8 Correct 2222 ms 98920 KB Output is correct
9 Runtime error 2407 ms 131076 KB Execution killed with signal 9
10 Runtime error 100 ms 80888 KB Execution killed with signal 11
11 Runtime error 125 ms 66748 KB Execution killed with signal 11
12 Runtime error 123 ms 70940 KB Execution killed with signal 11
13 Runtime error 103 ms 71816 KB Execution killed with signal 11
14 Runtime error 127 ms 70432 KB Execution killed with signal 11
15 Runtime error 108 ms 81032 KB Execution killed with signal 11
16 Runtime error 123 ms 95748 KB Execution killed with signal 11
17 Runtime error 116 ms 91880 KB Execution killed with signal 11