oj.uz

Submission #524338

# Submission time Handle Problem Language Result Execution time Memory
524338 2022-02-09T04:29:51 Z keertan Regions (IOI09_regions) C++17
14 / 100
 1529 ms 131076 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];
unordered_map<int,int> mp[25001];
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<<" ";
    int cur=0,cur1=0;
    for (int lg=(1ll<<18);lg;lg>>=1){
      if (sz(ctin[p])>=cur+lg && ctin[p][cur+lg-1]<tin[it]){
        cur+=lg;
      }
      if (sz(ctout[p])>=cur1+lg && ctout[p][cur1+lg-1]<=tin[it]){
        cur1+=lg;
      }
    }
    //cerr<<cur<<" "<<cur1;
    ans+=cur-cur1;
  }
  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;
  vector<int>f(r+1);
  cin>>c[1];
  f[c[1]]++;
  for (int i=2,x,p;i<=n;i++){
    cin>>p>>x;
    c[i]=x;
    f[x]++;
    adj[p].push_back(i);
  }
  for (int i=0;i<=r;i++){
    ctin[i].reserve(f[i]+2);
    ctout[i].reserve(f[i]+2);
    col[i].reserve(f[i]+2);
  }
  dfs(1);
  
  for (int i=1;i<=r;i++){
    if (sz(col[i])<=200){
      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[euler[j]][i]+=ok[j]-!!(euler[j]==i);
        }
      }
    }
  }
  for (int r,r1;q;q--){
    cin>>r>>r1;
    if (sz(col[r])>=200){cout<<mp[r1][r]<<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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23368 KB Output is correct
2 Correct 12 ms 23412 KB Output is correct
3 Correct 13 ms 23368 KB Output is correct
4 Correct 14 ms 23400 KB Output is correct
5 Correct 18 ms 23516 KB Output is correct
6 Correct 34 ms 25868 KB Output is correct
7 Correct 42 ms 24520 KB Output is correct
8 Correct 53 ms 25160 KB Output is correct
9 Correct 101 ms 28104 KB Output is correct
10 Correct 209 ms 31348 KB Output is correct
11 Correct 236 ms 27840 KB Output is correct
12 Correct 409 ms 33396 KB Output is correct
13 Correct 415 ms 29764 KB Output is correct
14 Correct 363 ms 27072 KB Output is correct
15 Incorrect 495 ms 30852 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1016 ms 30520 KB Output isn't correct
2 Incorrect 801 ms 29192 KB Output isn't correct
3 Incorrect 1529 ms 34416 KB Output isn't correct
4 Runtime error 927 ms 131076 KB Execution killed with signal 9
5 Runtime error 1284 ms 131076 KB Execution killed with signal 9
6 Runtime error 1002 ms 131076 KB Execution killed with signal 9
7 Runtime error 1030 ms 131076 KB Execution killed with signal 9
8 Runtime error 1070 ms 131076 KB Execution killed with signal 9
9 Runtime error 1281 ms 131076 KB Execution killed with signal 9
10 Runtime error 96 ms 86264 KB Execution killed with signal 11
11 Runtime error 115 ms 73920 KB Execution killed with signal 11
12 Runtime error 116 ms 76148 KB Execution killed with signal 11
13 Runtime error 104 ms 77136 KB Execution killed with signal 11
14 Runtime error 118 ms 76628 KB Execution killed with signal 11
15 Runtime error 122 ms 87008 KB Execution killed with signal 11
16 Runtime error 113 ms 101948 KB Execution killed with signal 11
17 Runtime error 117 ms 98284 KB Execution killed with signal 11