oj.uz

Submission #524161

# Submission time Handle Problem Language Result Execution time Memory
524161 2022-02-08T18:07:20 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2804 ms 98684 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])>=300){
      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 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 14 ms 22096 KB Output is correct
6 Correct 32 ms 22332 KB Output is correct
7 Correct 27 ms 22220 KB Output is correct
8 Correct 49 ms 22316 KB Output is correct
9 Correct 53 ms 22980 KB Output is correct
10 Correct 81 ms 23068 KB Output is correct
11 Correct 140 ms 23616 KB Output is correct
12 Correct 149 ms 24396 KB Output is correct
13 Correct 187 ms 24116 KB Output is correct
14 Correct 213 ms 24780 KB Output is correct
15 Correct 326 ms 28272 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 29456 KB Output is correct
2 Correct 1102 ms 28368 KB Output is correct
3 Correct 1718 ms 34228 KB Output is correct
4 Correct 268 ms 25688 KB Output is correct
5 Correct 365 ms 28252 KB Output is correct
6 Correct 672 ms 50620 KB Output is correct
7 Correct 1176 ms 59812 KB Output is correct
8 Correct 2163 ms 98684 KB Output is correct
9 Correct 2804 ms 84556 KB Output is correct
10 Runtime error 100 ms 80832 KB Execution killed with signal 11
11 Runtime error 108 ms 66752 KB Execution killed with signal 11
12 Runtime error 115 ms 71004 KB Execution killed with signal 11
13 Runtime error 104 ms 71840 KB Execution killed with signal 11
14 Runtime error 115 ms 70408 KB Execution killed with signal 11
15 Runtime error 117 ms 81048 KB Execution killed with signal 11
16 Runtime error 113 ms 95680 KB Execution killed with signal 11
17 Runtime error 114 ms 91796 KB Execution killed with signal 11