oj.uz

답안 #524127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524127 2022-02-08T16:41:56 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2028 ms 96560 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])>=60000){
      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 21960 KB Output is correct
2 Correct 12 ms 21960 KB Output is correct
3 Correct 14 ms 22068 KB Output is correct
4 Correct 17 ms 22088 KB Output is correct
5 Correct 22 ms 22120 KB Output is correct
6 Correct 33 ms 22256 KB Output is correct
7 Correct 42 ms 22216 KB Output is correct
8 Correct 48 ms 22424 KB Output is correct
9 Correct 58 ms 22976 KB Output is correct
10 Correct 102 ms 23332 KB Output is correct
11 Correct 146 ms 23684 KB Output is correct
12 Correct 153 ms 24564 KB Output is correct
13 Correct 200 ms 24432 KB Output is correct
14 Correct 229 ms 24972 KB Output is correct
15 Correct 308 ms 28368 KB Output is correct

Subtask #2
45.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1010 ms 30188 KB Output is correct
2 Correct 1191 ms 29144 KB Output is correct
3 Correct 2028 ms 34676 KB Output is correct
4 Correct 297 ms 25924 KB Output is correct
5 Correct 360 ms 28548 KB Output is correct
6 Correct 609 ms 28412 KB Output is correct
7 Correct 837 ms 29072 KB Output is correct
8 Correct 884 ms 37808 KB Output is correct
9 Correct 1790 ms 43492 KB Output is correct
10 Runtime error 115 ms 82540 KB Execution killed with signal 11
11 Runtime error 120 ms 69088 KB Execution killed with signal 11
12 Runtime error 119 ms 73300 KB Execution killed with signal 11
13 Runtime error 108 ms 74116 KB Execution killed with signal 11
14 Runtime error 120 ms 72980 KB Execution killed with signal 11
15 Runtime error 108 ms 82496 KB Execution killed with signal 11
16 Runtime error 113 ms 96560 KB Execution killed with signal 11
17 Runtime error 130 ms 93184 KB Execution killed with signal 11