oj.uz

답안 #524329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524329 2022-02-09T04:21:33 Z keertan Regions (IOI09_regions) C++17
0 / 100
 3148 ms 110212 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].resize(f[i]+2);
    ctout[i].resize(f[i]+2);
    col[i].resize(f[i]+2);
  }
  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[euler[j]][i]+=ok[j]-!!(euler[j]==i);
        }
      }
    }
  }
  for (int r,r1;q;q--){
    cin>>r>>r1;
    if (sz(col[r])>=512){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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23368 KB Output isn't correct
2 Incorrect 13 ms 23312 KB Output isn't correct
3 Incorrect 16 ms 23392 KB Output isn't correct
4 Incorrect 17 ms 23368 KB Output isn't correct
5 Incorrect 22 ms 23496 KB Output isn't correct
6 Incorrect 34 ms 23432 KB Output isn't correct
7 Incorrect 41 ms 23496 KB Output isn't correct
8 Incorrect 37 ms 23624 KB Output isn't correct
9 Incorrect 69 ms 24136 KB Output isn't correct
10 Incorrect 94 ms 24136 KB Output isn't correct
11 Incorrect 135 ms 24648 KB Output isn't correct
12 Incorrect 137 ms 25288 KB Output isn't correct
13 Incorrect 187 ms 24828 KB Output isn't correct
14 Incorrect 299 ms 25536 KB Output isn't correct
15 Incorrect 364 ms 28956 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1914 ms 30608 KB Output isn't correct
2 Incorrect 1640 ms 29888 KB Output isn't correct
3 Incorrect 3126 ms 33072 KB Output isn't correct
4 Incorrect 273 ms 25920 KB Output isn't correct
5 Incorrect 262 ms 28148 KB Output isn't correct
6 Incorrect 743 ms 46104 KB Output isn't correct
7 Incorrect 1321 ms 50460 KB Output isn't correct
8 Incorrect 1665 ms 77892 KB Output isn't correct
9 Incorrect 3148 ms 93208 KB Output isn't correct
10 Runtime error 118 ms 90824 KB Execution killed with signal 11
11 Runtime error 137 ms 79584 KB Execution killed with signal 11
12 Runtime error 156 ms 81896 KB Execution killed with signal 11
13 Runtime error 119 ms 82844 KB Execution killed with signal 11
14 Runtime error 141 ms 82544 KB Execution killed with signal 11
15 Runtime error 126 ms 94324 KB Execution killed with signal 11
16 Runtime error 142 ms 110212 KB Execution killed with signal 11
17 Runtime error 124 ms 104488 KB Execution killed with signal 11