oj.uz

답안 #524125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524125 2022-02-08T16:40:20 Z keertan Regions (IOI09_regions) C++17
60 / 100
 1917 ms 96600 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#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 int64_t 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];
int stnd[N],ennd[N];
map<pair<int,int>,int> mp;
void dfs(int u){
  tin[u]=tmr;
  stnd[tmr]=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;
  ennd[tmr++]=u;
  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;
}
int gh;
void dfs1(int u,int x){
  for (const int& it:adj[u]){
    if (x){
      mp[{gh,c[u]}]+=x;
    }
    dfs1(it,x+!!(c[it]==gh));
  }
}
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])>=100000){
      gh=i;
      dfs1(i,0);
    }
  }
  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();}
}

Compilation message

regions.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 22088 KB Output is correct
2 Correct 13 ms 21976 KB Output is correct
3 Correct 15 ms 22024 KB Output is correct
4 Correct 17 ms 22092 KB Output is correct
5 Correct 23 ms 22268 KB Output is correct
6 Correct 31 ms 22272 KB Output is correct
7 Correct 40 ms 22252 KB Output is correct
8 Correct 28 ms 22320 KB Output is correct
9 Correct 65 ms 23092 KB Output is correct
10 Correct 95 ms 23208 KB Output is correct
11 Correct 124 ms 23748 KB Output is correct
12 Correct 165 ms 24540 KB Output is correct
13 Correct 200 ms 24304 KB Output is correct
14 Correct 271 ms 25100 KB Output is correct
15 Correct 278 ms 28228 KB Output is correct

Subtask #2
45.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1065 ms 30180 KB Output is correct
2 Correct 1286 ms 29300 KB Output is correct
3 Correct 1896 ms 34528 KB Output is correct
4 Correct 211 ms 26068 KB Output is correct
5 Correct 397 ms 28516 KB Output is correct
6 Correct 545 ms 28512 KB Output is correct
7 Correct 718 ms 29100 KB Output is correct
8 Correct 1008 ms 37840 KB Output is correct
9 Correct 1917 ms 43576 KB Output is correct
10 Runtime error 100 ms 82532 KB Execution killed with signal 11
11 Runtime error 110 ms 69156 KB Execution killed with signal 11
12 Runtime error 122 ms 73400 KB Execution killed with signal 11
13 Runtime error 107 ms 74048 KB Execution killed with signal 11
14 Runtime error 116 ms 72872 KB Execution killed with signal 11
15 Runtime error 120 ms 82496 KB Execution killed with signal 11
16 Runtime error 126 ms 96600 KB Execution killed with signal 11
17 Runtime error 118 ms 93120 KB Execution killed with signal 11