oj.uz

답안 #524160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524160 2022-02-08T18:06:35 Z keertan Regions (IOI09_regions) C++17
60 / 100
 1997 ms 98832 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);
  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 (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 12 ms 21960 KB Output is correct
2 Correct 12 ms 21980 KB Output is correct
3 Correct 12 ms 21960 KB Output is correct
4 Correct 16 ms 21960 KB Output is correct
5 Correct 18 ms 22140 KB Output is correct
6 Correct 34 ms 22220 KB Output is correct
7 Correct 38 ms 22284 KB Output is correct
8 Correct 41 ms 22360 KB Output is correct
9 Correct 75 ms 22952 KB Output is correct
10 Correct 87 ms 23160 KB Output is correct
11 Correct 113 ms 23536 KB Output is correct
12 Correct 159 ms 24332 KB Output is correct
13 Correct 184 ms 24140 KB Output is correct
14 Correct 260 ms 24808 KB Output is correct
15 Correct 335 ms 28016 KB Output is correct

Subtask #2
45.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 834 ms 29780 KB Output is correct
2 Correct 1185 ms 28308 KB Output is correct
3 Correct 1860 ms 34088 KB Output is correct
4 Correct 227 ms 25848 KB Output is correct
5 Correct 395 ms 28404 KB Output is correct
6 Correct 857 ms 50648 KB Output is correct
7 Correct 1090 ms 45472 KB Output is correct
8 Correct 1997 ms 98832 KB Output is correct
9 Correct 1835 ms 42272 KB Output is correct
10 Runtime error 97 ms 80868 KB Execution killed with signal 11
11 Runtime error 107 ms 66688 KB Execution killed with signal 11
12 Runtime error 119 ms 70984 KB Execution killed with signal 11
13 Runtime error 105 ms 71784 KB Execution killed with signal 11
14 Runtime error 120 ms 70508 KB Execution killed with signal 11
15 Runtime error 108 ms 81012 KB Execution killed with signal 11
16 Runtime error 118 ms 95680 KB Execution killed with signal 11
17 Runtime error 112 ms 91840 KB Execution killed with signal 11