oj.uz

Submission #524126

# Submission time Handle Problem Language Result Execution time Memory
524126 2022-02-08T16:41:06 Z keertan Regions (IOI09_regions) C++17
60 / 100
 1975 ms 96576 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])>=70000){
      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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22044 KB Output is correct
2 Correct 13 ms 22012 KB Output is correct
3 Correct 19 ms 21972 KB Output is correct
4 Correct 17 ms 22088 KB Output is correct
5 Correct 16 ms 22128 KB Output is correct
6 Correct 35 ms 22228 KB Output is correct
7 Correct 45 ms 22324 KB Output is correct
8 Correct 45 ms 22400 KB Output is correct
9 Correct 54 ms 23008 KB Output is correct
10 Correct 94 ms 23360 KB Output is correct
11 Correct 124 ms 23688 KB Output is correct
12 Correct 156 ms 24548 KB Output is correct
13 Correct 127 ms 24504 KB Output is correct
14 Correct 239 ms 24988 KB Output is correct
15 Correct 300 ms 28500 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 30120 KB Output is correct
2 Correct 1159 ms 29024 KB Output is correct
3 Correct 1614 ms 34600 KB Output is correct
4 Correct 284 ms 25968 KB Output is correct
5 Correct 412 ms 28540 KB Output is correct
6 Correct 564 ms 28404 KB Output is correct
7 Correct 796 ms 29184 KB Output is correct
8 Correct 1026 ms 37836 KB Output is correct
9 Correct 1975 ms 43404 KB Output is correct
10 Runtime error 113 ms 82496 KB Execution killed with signal 11
11 Runtime error 108 ms 69172 KB Execution killed with signal 11
12 Runtime error 126 ms 73400 KB Execution killed with signal 11
13 Runtime error 116 ms 74268 KB Execution killed with signal 11
14 Runtime error 129 ms 72864 KB Execution killed with signal 11
15 Runtime error 122 ms 82544 KB Execution killed with signal 11
16 Runtime error 115 ms 96576 KB Execution killed with signal 11
17 Runtime error 110 ms 93168 KB Execution killed with signal 11