oj.uz

답안 #524189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524189 2022-02-08T18:33:46 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2376 ms 96744 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[p].begin();
    ans-=upper_bound(all(ctout[p]),tin[it])-ctout[p].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])>=400){
      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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 21960 KB Output is correct
2 Correct 12 ms 22040 KB Output is correct
3 Correct 12 ms 22052 KB Output is correct
4 Correct 19 ms 22056 KB Output is correct
5 Correct 19 ms 22088 KB Output is correct
6 Correct 30 ms 22140 KB Output is correct
7 Correct 35 ms 22088 KB Output is correct
8 Correct 42 ms 22216 KB Output is correct
9 Correct 73 ms 22600 KB Output is correct
10 Correct 117 ms 22728 KB Output is correct
11 Correct 139 ms 23060 KB Output is correct
12 Correct 143 ms 23604 KB Output is correct
13 Correct 148 ms 23368 KB Output is correct
14 Correct 267 ms 24112 KB Output is correct
15 Correct 211 ms 27240 KB Output is correct

Subtask #2
45.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1720 ms 28520 KB Output is correct
2 Correct 1839 ms 27384 KB Output is correct
3 Correct 2376 ms 30828 KB Output is correct
4 Correct 280 ms 24244 KB Output is correct
5 Correct 345 ms 26184 KB Output is correct
6 Correct 1571 ms 49052 KB Output is correct
7 Correct 1433 ms 44656 KB Output is correct
8 Correct 2215 ms 96744 KB Output is correct
9 Correct 1594 ms 34212 KB Output is correct
10 Runtime error 96 ms 80824 KB Execution killed with signal 11
11 Runtime error 117 ms 66896 KB Execution killed with signal 11
12 Runtime error 115 ms 70912 KB Execution killed with signal 11
13 Runtime error 108 ms 71960 KB Execution killed with signal 11
14 Runtime error 113 ms 70460 KB Execution killed with signal 11
15 Runtime error 106 ms 80980 KB Execution killed with signal 11
16 Runtime error 114 ms 95692 KB Execution killed with signal 11
17 Runtime error 116 ms 91952 KB Execution killed with signal 11