oj.uz

Submission #524155

# Submission time Handle Problem Language Result Execution time Memory
524155 2022-02-08T17:56:25 Z keertan Regions (IOI09_regions) C++17
3 / 100
 3612 ms 79760 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:adj[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];
        }
      }
    }
  }
  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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 21960 KB Output isn't correct
2 Incorrect 11 ms 21960 KB Output isn't correct
3 Incorrect 15 ms 22000 KB Output isn't correct
4 Incorrect 19 ms 22072 KB Output isn't correct
5 Incorrect 20 ms 22124 KB Output isn't correct
6 Correct 33 ms 22244 KB Output is correct
7 Incorrect 25 ms 22228 KB Output isn't correct
8 Incorrect 33 ms 22288 KB Output isn't correct
9 Correct 70 ms 22984 KB Output is correct
10 Incorrect 77 ms 23120 KB Output isn't correct
11 Incorrect 132 ms 23584 KB Output isn't correct
12 Incorrect 92 ms 24248 KB Output isn't correct
13 Incorrect 213 ms 24080 KB Output isn't correct
14 Incorrect 279 ms 24652 KB Output isn't correct
15 Correct 347 ms 28044 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1199 ms 29220 KB Output isn't correct
2 Incorrect 1289 ms 28148 KB Output isn't correct
3 Incorrect 2121 ms 33948 KB Output isn't correct
4 Incorrect 265 ms 25632 KB Output isn't correct
5 Incorrect 463 ms 28224 KB Output isn't correct
6 Incorrect 634 ms 34836 KB Output isn't correct
7 Incorrect 902 ms 28236 KB Output isn't correct
8 Incorrect 1060 ms 39096 KB Output isn't correct
9 Incorrect 1828 ms 41868 KB Output isn't correct
10 Incorrect 3058 ms 50064 KB Output isn't correct
11 Incorrect 3612 ms 45428 KB Output isn't correct
12 Incorrect 1455 ms 40212 KB Output isn't correct
13 Incorrect 1765 ms 42616 KB Output isn't correct
14 Incorrect 2343 ms 64988 KB Output isn't correct
15 Incorrect 2954 ms 52992 KB Output isn't correct
16 Incorrect 3022 ms 60160 KB Output isn't correct
17 Incorrect 3497 ms 79760 KB Output isn't correct