oj.uz

Submission #524192

# Submission time Handle Problem Language Result Execution time Memory
524192 2022-02-08T18:37:15 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2610 ms 96628 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<<" ";
    ans+=lower_bound(all(ctin[p]),tin[it])-ctin[p].begin();
    ans-=upper_bound(all(ctout[p]),tin[it])-ctout[p].begin();
  }
  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]){
    ans+=upper_bound(all(ctin[chld]),tout[it])-ctin[chld].begin();
    ans-=upper_bound(all(ctin[chld]),tin[it])-ctin[chld].begin();
  }
  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])>=400){
      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 (sz(col[r])>=512){cout<<mp[{r,r1}]<<endl;continue;}
    else{
      int ans=0;
  //cerr<<"gh";
  //cout<<tin[1]<<" "<<tout[1]<<"\n";

  for (const int& it:col[r]){
    ans+=upper_bound(all(ctin[r1]),tout[it])-ctin[r1].begin();
    ans-=upper_bound(all(ctin[r1]),tin[it])-ctin[r1].begin();
  }
  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 12 ms 21992 KB Output is correct
3 Correct 13 ms 21960 KB Output is correct
4 Correct 14 ms 21960 KB Output is correct
5 Correct 18 ms 22024 KB Output is correct
6 Correct 29 ms 22136 KB Output is correct
7 Correct 39 ms 22088 KB Output is correct
8 Correct 37 ms 22216 KB Output is correct
9 Correct 59 ms 22600 KB Output is correct
10 Correct 76 ms 22728 KB Output is correct
11 Correct 116 ms 23240 KB Output is correct
12 Correct 138 ms 23692 KB Output is correct
13 Correct 163 ms 23368 KB Output is correct
14 Correct 211 ms 24128 KB Output is correct
15 Correct 260 ms 27328 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1637 ms 28648 KB Output is correct
2 Correct 1925 ms 27304 KB Output is correct
3 Correct 2610 ms 30772 KB Output is correct
4 Correct 236 ms 24372 KB Output is correct
5 Correct 294 ms 26184 KB Output is correct
6 Correct 1407 ms 49092 KB Output is correct
7 Correct 1700 ms 44688 KB Output is correct
8 Correct 2213 ms 96628 KB Output is correct
9 Correct 1643 ms 34212 KB Output is correct
10 Runtime error 101 ms 80788 KB Execution killed with signal 11
11 Runtime error 109 ms 66700 KB Execution killed with signal 11
12 Runtime error 115 ms 70912 KB Execution killed with signal 11
13 Runtime error 110 ms 71748 KB Execution killed with signal 11
14 Runtime error 112 ms 70460 KB Execution killed with signal 11
15 Runtime error 106 ms 81044 KB Execution killed with signal 11
16 Runtime error 126 ms 95784 KB Execution killed with signal 11
17 Runtime error 108 ms 91804 KB Execution killed with signal 11