oj.uz

Submission #524186

# Submission time Handle Problem Language Result Execution time Memory
524186 2022-02-08T18:31:34 Z keertan Regions (IOI09_regions) C++17
0 / 100
 2543 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(ctout[p]),tin[it])-ctout[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 12 ms 22000 KB Output isn't correct
2 Incorrect 12 ms 22024 KB Output isn't correct
3 Incorrect 13 ms 22016 KB Output isn't correct
4 Incorrect 16 ms 21960 KB Output isn't correct
5 Incorrect 18 ms 22088 KB Output isn't correct
6 Incorrect 31 ms 22088 KB Output isn't correct
7 Incorrect 35 ms 22088 KB Output isn't correct
8 Incorrect 45 ms 22216 KB Output isn't correct
9 Incorrect 45 ms 22696 KB Output isn't correct
10 Incorrect 71 ms 22652 KB Output isn't correct
11 Incorrect 119 ms 23112 KB Output isn't correct
12 Incorrect 95 ms 23628 KB Output isn't correct
13 Incorrect 145 ms 23368 KB Output isn't correct
14 Incorrect 186 ms 24156 KB Output isn't correct
15 Incorrect 256 ms 27180 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1427 ms 28572 KB Output isn't correct
2 Incorrect 2131 ms 27496 KB Output isn't correct
3 Incorrect 2543 ms 30784 KB Output isn't correct
4 Incorrect 289 ms 24248 KB Output isn't correct
5 Incorrect 338 ms 26056 KB Output isn't correct
6 Incorrect 1331 ms 25848 KB Output isn't correct
7 Incorrect 1406 ms 27196 KB Output isn't correct
8 Incorrect 774 ms 33288 KB Output isn't correct
9 Incorrect 1941 ms 34212 KB Output isn't correct
10 Runtime error 104 ms 80840 KB Execution killed with signal 11
11 Runtime error 108 ms 66720 KB Execution killed with signal 11
12 Runtime error 116 ms 70948 KB Execution killed with signal 11
13 Runtime error 117 ms 71836 KB Execution killed with signal 11
14 Runtime error 121 ms 70444 KB Execution killed with signal 11
15 Runtime error 104 ms 80980 KB Execution killed with signal 11
16 Runtime error 111 ms 95680 KB Execution killed with signal 11
17 Runtime error 111 ms 91888 KB Execution killed with signal 11