oj.uz

Submission #523996

# Submission time Handle Problem Language Result Execution time Memory
523996 2022-02-08T14:13:25 Z keertan Regions (IOI09_regions) C++17
60 / 100
 1965 ms 115736 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[N];
int stnd[N],ennd[N];
void dfs(int u,int v){
  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]){
    if (it==v){continue;}
    dfs(it,u);
  }
  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;
}
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,1);
  map<pair<int,int>,int> mp;
  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 18 ms 28492 KB Output is correct
2 Correct 17 ms 28488 KB Output is correct
3 Correct 18 ms 28488 KB Output is correct
4 Correct 20 ms 28488 KB Output is correct
5 Correct 24 ms 28536 KB Output is correct
6 Correct 36 ms 28736 KB Output is correct
7 Correct 44 ms 28772 KB Output is correct
8 Correct 54 ms 28892 KB Output is correct
9 Correct 66 ms 29540 KB Output is correct
10 Correct 90 ms 29704 KB Output is correct
11 Correct 129 ms 30216 KB Output is correct
12 Correct 155 ms 31036 KB Output is correct
13 Correct 176 ms 30756 KB Output is correct
14 Correct 235 ms 31752 KB Output is correct
15 Correct 287 ms 35464 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 36704 KB Output is correct
2 Correct 1156 ms 35400 KB Output is correct
3 Correct 1965 ms 41492 KB Output is correct
4 Correct 259 ms 32664 KB Output is correct
5 Correct 387 ms 35324 KB Output is correct
6 Correct 607 ms 34860 KB Output is correct
7 Correct 817 ms 35848 KB Output is correct
8 Correct 1212 ms 45364 KB Output is correct
9 Correct 1896 ms 50256 KB Output is correct
10 Runtime error 127 ms 98400 KB Execution killed with signal 11
11 Runtime error 139 ms 82356 KB Execution killed with signal 11
12 Runtime error 132 ms 86548 KB Execution killed with signal 11
13 Runtime error 126 ms 87876 KB Execution killed with signal 11
14 Runtime error 127 ms 86232 KB Execution killed with signal 11
15 Runtime error 117 ms 97832 KB Execution killed with signal 11
16 Runtime error 129 ms 115736 KB Execution killed with signal 11
17 Runtime error 131 ms 111444 KB Execution killed with signal 11