oj.uz

답안 #524123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524123 2022-02-08T16:39:21 Z keertan Regions (IOI09_regions) C++17
50 / 100
 1967 ms 96636 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])>=5000){
      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 13 ms 21960 KB Output is correct
3 Correct 15 ms 21960 KB Output is correct
4 Correct 17 ms 22072 KB Output is correct
5 Correct 20 ms 22088 KB Output is correct
6 Correct 28 ms 22268 KB Output is correct
7 Correct 39 ms 22312 KB Output is correct
8 Correct 47 ms 22376 KB Output is correct
9 Correct 71 ms 22920 KB Output is correct
10 Correct 85 ms 23172 KB Output is correct
11 Correct 141 ms 23728 KB Output is correct
12 Correct 161 ms 24564 KB Output is correct
13 Correct 164 ms 24388 KB Output is correct
14 Correct 226 ms 25240 KB Output is correct
15 Correct 282 ms 28280 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1123 ms 30712 KB Output isn't correct
2 Correct 1220 ms 29140 KB Output is correct
3 Incorrect 1850 ms 34536 KB Output isn't correct
4 Correct 300 ms 26124 KB Output is correct
5 Correct 399 ms 28580 KB Output is correct
6 Correct 497 ms 28280 KB Output is correct
7 Correct 761 ms 28996 KB Output is correct
8 Correct 998 ms 37820 KB Output is correct
9 Correct 1967 ms 43512 KB Output is correct
10 Runtime error 100 ms 82444 KB Execution killed with signal 11
11 Runtime error 124 ms 69124 KB Execution killed with signal 11
12 Runtime error 117 ms 73280 KB Execution killed with signal 11
13 Runtime error 107 ms 74040 KB Execution killed with signal 11
14 Runtime error 115 ms 72892 KB Execution killed with signal 11
15 Runtime error 117 ms 82532 KB Execution killed with signal 11
16 Runtime error 114 ms 96636 KB Execution killed with signal 11
17 Runtime error 111 ms 93136 KB Execution killed with signal 11