oj.uz

Submission #524195

# Submission time Handle Problem Language Result Execution time Memory
524195 2022-02-08T18:39:22 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2574 ms 96832 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<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 12 ms 21960 KB Output is correct
2 Correct 12 ms 21960 KB Output is correct
3 Correct 13 ms 21960 KB Output is correct
4 Correct 15 ms 21948 KB Output is correct
5 Correct 17 ms 22088 KB Output is correct
6 Correct 31 ms 22088 KB Output is correct
7 Correct 41 ms 22088 KB Output is correct
8 Correct 42 ms 22216 KB Output is correct
9 Correct 55 ms 22724 KB Output is correct
10 Correct 88 ms 22644 KB Output is correct
11 Correct 128 ms 23112 KB Output is correct
12 Correct 140 ms 23724 KB Output is correct
13 Correct 166 ms 23368 KB Output is correct
14 Correct 261 ms 24024 KB Output is correct
15 Correct 272 ms 27244 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1765 ms 28524 KB Output is correct
2 Correct 1784 ms 27336 KB Output is correct
3 Correct 2574 ms 30892 KB Output is correct
4 Correct 204 ms 24268 KB Output is correct
5 Correct 364 ms 26088 KB Output is correct
6 Correct 1458 ms 49048 KB Output is correct
7 Correct 1519 ms 44700 KB Output is correct
8 Correct 2461 ms 96832 KB Output is correct
9 Correct 1623 ms 34240 KB Output is correct
10 Runtime error 110 ms 80904 KB Execution killed with signal 11
11 Runtime error 105 ms 66780 KB Execution killed with signal 11
12 Runtime error 113 ms 70976 KB Execution killed with signal 11
13 Runtime error 101 ms 71792 KB Execution killed with signal 11
14 Runtime error 114 ms 70512 KB Execution killed with signal 11
15 Runtime error 116 ms 81228 KB Execution killed with signal 11
16 Runtime error 113 ms 95700 KB Execution killed with signal 11
17 Runtime error 107 ms 91892 KB Execution killed with signal 11