oj.uz

Submission #524187

# Submission time Handle Problem Language Result Execution time Memory
524187 2022-02-08T18:32:23 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2615 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<<" ";
    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])>=512){
      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 if (sz(col[r])<sz(col[r1])){
      cout<<parent(r,r1)<<endl;
    }
    else{
      cout<<child(r,r1)<<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 21952 KB Output is correct
3 Correct 13 ms 21960 KB Output is correct
4 Correct 15 ms 21960 KB Output is correct
5 Correct 17 ms 22088 KB Output is correct
6 Correct 31 ms 22088 KB Output is correct
7 Correct 33 ms 22088 KB Output is correct
8 Correct 32 ms 22172 KB Output is correct
9 Correct 55 ms 22704 KB Output is correct
10 Correct 94 ms 22740 KB Output is correct
11 Correct 128 ms 22984 KB Output is correct
12 Correct 155 ms 23752 KB Output is correct
13 Correct 193 ms 23440 KB Output is correct
14 Correct 271 ms 24116 KB Output is correct
15 Correct 251 ms 27236 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1682 ms 28584 KB Output is correct
2 Correct 1599 ms 27328 KB Output is correct
3 Correct 2615 ms 30816 KB Output is correct
4 Correct 241 ms 24256 KB Output is correct
5 Correct 321 ms 26124 KB Output is correct
6 Correct 1107 ms 25752 KB Output is correct
7 Correct 1301 ms 27244 KB Output is correct
8 Correct 961 ms 33284 KB Output is correct
9 Correct 1896 ms 34216 KB Output is correct
10 Runtime error 109 ms 80788 KB Execution killed with signal 11
11 Runtime error 124 ms 66892 KB Execution killed with signal 11
12 Runtime error 133 ms 70916 KB Execution killed with signal 11
13 Runtime error 124 ms 71828 KB Execution killed with signal 11
14 Runtime error 131 ms 70456 KB Execution killed with signal 11
15 Runtime error 108 ms 80920 KB Execution killed with signal 11
16 Runtime error 119 ms 95680 KB Execution killed with signal 11
17 Runtime error 110 ms 91828 KB Execution killed with signal 11