oj.uz

Submission #524159

# Submission time Handle Problem Language Result Execution time Memory
524159 2022-02-08T18:05:39 Z keertan Regions (IOI09_regions) C++17
60 / 100
 1836 ms 95680 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])>=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[{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 12 ms 22060 KB Output is correct
4 Correct 14 ms 22060 KB Output is correct
5 Correct 17 ms 22116 KB Output is correct
6 Correct 26 ms 22216 KB Output is correct
7 Correct 40 ms 22240 KB Output is correct
8 Correct 49 ms 22436 KB Output is correct
9 Correct 65 ms 22924 KB Output is correct
10 Correct 104 ms 23104 KB Output is correct
11 Correct 123 ms 23612 KB Output is correct
12 Correct 165 ms 24300 KB Output is correct
13 Correct 188 ms 24192 KB Output is correct
14 Correct 233 ms 24752 KB Output is correct
15 Correct 303 ms 28156 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 29824 KB Output is correct
2 Correct 997 ms 28492 KB Output is correct
3 Correct 1836 ms 34360 KB Output is correct
4 Correct 253 ms 25784 KB Output is correct
5 Correct 380 ms 28316 KB Output is correct
6 Correct 572 ms 35236 KB Output is correct
7 Correct 674 ms 28444 KB Output is correct
8 Correct 1066 ms 39192 KB Output is correct
9 Correct 1682 ms 42356 KB Output is correct
10 Runtime error 103 ms 80852 KB Execution killed with signal 11
11 Runtime error 114 ms 66716 KB Execution killed with signal 11
12 Runtime error 119 ms 70940 KB Execution killed with signal 11
13 Runtime error 103 ms 71744 KB Execution killed with signal 11
14 Runtime error 113 ms 70404 KB Execution killed with signal 11
15 Runtime error 112 ms 80964 KB Execution killed with signal 11
16 Runtime error 118 ms 95680 KB Execution killed with signal 11
17 Runtime error 121 ms 91868 KB Execution killed with signal 11