oj.uz

답안 #524169

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524169 2022-02-08T18:16:43 Z keertan Regions (IOI09_regions) C++17
50 / 100
 2623 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];
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<<" ";
    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]){
    //cerr<<it<<" ";
    int cur=0,cur1=0;
    for (int lg=(1ll<<18);lg;lg>>=1){
      if (sz(ctin[chld])>=cur+lg && ctin[chld][cur+lg-1]<=tin[it]){
        cur+=lg;
      }
      if (sz(ctin[chld])>=cur1+lg && ctin[chld][cur1+lg-1]<=tout[it]){
        cur1+=lg;
      }
    }
    // cerr<<cur<<" "<<cur1<<"\n";
      ans+=cur1-cur;
  }
  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);
  int f=sqrt(r);
  for (int i=1;i<=r;i++){
    if (sz(col[i])>=f){
      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 (mp.find({r,r1})!=mp.end()){cout<<mp[{r,r1}]<<endl;continue;}
    int ans=0;
    if (sz(col[r])<sz(col[r1])){
      ans=parent(r,r1);
    }
    else{
     // cerr<<"fck\n";
      ans=child(r,r1);
    }
    mp[{r,r1}]=ans;
    cout<<ans<<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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21960 KB Output is correct
2 Correct 12 ms 21960 KB Output is correct
3 Correct 14 ms 22012 KB Output is correct
4 Correct 16 ms 22088 KB Output is correct
5 Correct 19 ms 22216 KB Output is correct
6 Correct 25 ms 22248 KB Output is correct
7 Correct 41 ms 22600 KB Output is correct
8 Correct 49 ms 22856 KB Output is correct
9 Correct 114 ms 25620 KB Output is correct
10 Correct 396 ms 31776 KB Output is correct
11 Correct 406 ms 27636 KB Output is correct
12 Correct 843 ms 36540 KB Output is correct
13 Correct 865 ms 30716 KB Output is correct
14 Correct 613 ms 26696 KB Output is correct
15 Correct 1113 ms 31088 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1710 ms 30892 KB Output is correct
2 Correct 1760 ms 30372 KB Output is correct
3 Correct 2623 ms 34756 KB Output is correct
4 Correct 645 ms 47688 KB Output is correct
5 Correct 748 ms 46128 KB Output is correct
6 Correct 673 ms 50864 KB Output is correct
7 Correct 1550 ms 89512 KB Output is correct
8 Runtime error 1884 ms 131076 KB Execution killed with signal 9
9 Runtime error 2381 ms 131076 KB Execution killed with signal 9
10 Runtime error 95 ms 80852 KB Execution killed with signal 11
11 Runtime error 120 ms 66776 KB Execution killed with signal 11
12 Runtime error 118 ms 70924 KB Execution killed with signal 11
13 Runtime error 104 ms 71744 KB Execution killed with signal 11
14 Runtime error 112 ms 70504 KB Execution killed with signal 11
15 Runtime error 104 ms 81008 KB Execution killed with signal 11
16 Runtime error 130 ms 95840 KB Execution killed with signal 11
17 Runtime error 115 ms 91904 KB Execution killed with signal 11