oj.uz

Submission #524185

# Submission time Handle Problem Language Result Execution time Memory
524185 2022-02-08T18:30:14 Z keertan Regions (IOI09_regions) C++17
0 / 100
 2432 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[chld].begin();
    ans-=upper_bound(all(ctin[p]),tin[it])-ctin[chld].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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 21960 KB Output isn't correct
2 Incorrect 11 ms 21960 KB Output isn't correct
3 Incorrect 16 ms 21960 KB Output isn't correct
4 Incorrect 15 ms 21960 KB Output isn't correct
5 Incorrect 17 ms 22088 KB Output isn't correct
6 Incorrect 29 ms 22088 KB Output isn't correct
7 Incorrect 40 ms 22088 KB Output isn't correct
8 Incorrect 37 ms 22216 KB Output isn't correct
9 Incorrect 61 ms 22600 KB Output isn't correct
10 Incorrect 74 ms 22696 KB Output isn't correct
11 Incorrect 111 ms 23040 KB Output isn't correct
12 Incorrect 138 ms 23624 KB Output isn't correct
13 Incorrect 184 ms 23428 KB Output isn't correct
14 Incorrect 233 ms 24128 KB Output isn't correct
15 Incorrect 269 ms 27252 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1651 ms 28472 KB Output isn't correct
2 Incorrect 1716 ms 27424 KB Output isn't correct
3 Incorrect 2432 ms 30812 KB Output isn't correct
4 Incorrect 249 ms 24256 KB Output isn't correct
5 Incorrect 314 ms 26212 KB Output isn't correct
6 Incorrect 1120 ms 25788 KB Output isn't correct
7 Incorrect 1180 ms 27200 KB Output isn't correct
8 Incorrect 1014 ms 33316 KB Output isn't correct
9 Incorrect 1884 ms 34216 KB Output isn't correct
10 Runtime error 100 ms 80832 KB Execution killed with signal 11
11 Runtime error 111 ms 66700 KB Execution killed with signal 11
12 Runtime error 124 ms 70956 KB Execution killed with signal 11
13 Runtime error 107 ms 71784 KB Execution killed with signal 11
14 Runtime error 124 ms 70428 KB Execution killed with signal 11
15 Runtime error 117 ms 80960 KB Execution killed with signal 11
16 Runtime error 113 ms 95680 KB Execution killed with signal 11
17 Runtime error 111 ms 91808 KB Execution killed with signal 11