oj.uz

Submission #524164

# Submission time Handle Problem Language Result Execution time Memory
524164 2022-02-08T18:10:49 Z keertan Regions (IOI09_regions) C++17
60 / 100
 3951 ms 123192 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])>=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[{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 11 ms 21960 KB Output is correct
2 Correct 11 ms 21960 KB Output is correct
3 Correct 13 ms 21960 KB Output is correct
4 Correct 15 ms 22052 KB Output is correct
5 Correct 18 ms 22112 KB Output is correct
6 Correct 27 ms 22224 KB Output is correct
7 Correct 34 ms 22304 KB Output is correct
8 Correct 44 ms 22356 KB Output is correct
9 Correct 70 ms 22940 KB Output is correct
10 Correct 88 ms 23132 KB Output is correct
11 Correct 123 ms 23580 KB Output is correct
12 Correct 150 ms 24416 KB Output is correct
13 Correct 186 ms 24228 KB Output is correct
14 Correct 241 ms 24796 KB Output is correct
15 Correct 324 ms 28104 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 29916 KB Output is correct
2 Correct 1634 ms 29468 KB Output is correct
3 Correct 2798 ms 34832 KB Output is correct
4 Correct 182 ms 25880 KB Output is correct
5 Correct 356 ms 28392 KB Output is correct
6 Correct 814 ms 50624 KB Output is correct
7 Correct 1329 ms 65976 KB Output is correct
8 Correct 2188 ms 98672 KB Output is correct
9 Correct 3951 ms 123192 KB Output is correct
10 Runtime error 119 ms 80832 KB Execution killed with signal 11
11 Runtime error 110 ms 66708 KB Execution killed with signal 11
12 Runtime error 114 ms 70940 KB Execution killed with signal 11
13 Runtime error 116 ms 71744 KB Execution killed with signal 11
14 Runtime error 122 ms 70428 KB Execution killed with signal 11
15 Runtime error 105 ms 80964 KB Execution killed with signal 11
16 Runtime error 113 ms 95632 KB Execution killed with signal 11
17 Runtime error 128 ms 91796 KB Execution killed with signal 11