oj.uz

Submission #524119

# Submission time Handle Problem Language Result Execution time Memory
524119 2022-02-08T16:35:27 Z keertan Regions (IOI09_regions) C++17
60 / 100
 1763 ms 96556 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])>=450){
      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 14 ms 21960 KB Output is correct
2 Correct 14 ms 21960 KB Output is correct
3 Correct 16 ms 22032 KB Output is correct
4 Correct 18 ms 22084 KB Output is correct
5 Correct 17 ms 22108 KB Output is correct
6 Correct 22 ms 22264 KB Output is correct
7 Correct 29 ms 22272 KB Output is correct
8 Correct 44 ms 22304 KB Output is correct
9 Correct 67 ms 23020 KB Output is correct
10 Correct 105 ms 23160 KB Output is correct
11 Correct 100 ms 23900 KB Output is correct
12 Correct 146 ms 24556 KB Output is correct
13 Correct 187 ms 24384 KB Output is correct
14 Correct 205 ms 25068 KB Output is correct
15 Correct 321 ms 28300 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 30176 KB Output is correct
2 Correct 1239 ms 29104 KB Output is correct
3 Correct 1753 ms 34704 KB Output is correct
4 Correct 314 ms 25996 KB Output is correct
5 Correct 327 ms 28548 KB Output is correct
6 Correct 492 ms 28268 KB Output is correct
7 Correct 572 ms 29228 KB Output is correct
8 Correct 1008 ms 37904 KB Output is correct
9 Correct 1763 ms 43488 KB Output is correct
10 Runtime error 103 ms 82500 KB Execution killed with signal 11
11 Runtime error 108 ms 69124 KB Execution killed with signal 11
12 Runtime error 116 ms 73296 KB Execution killed with signal 11
13 Runtime error 126 ms 74040 KB Execution killed with signal 11
14 Runtime error 131 ms 72960 KB Execution killed with signal 11
15 Runtime error 108 ms 82500 KB Execution killed with signal 11
16 Runtime error 124 ms 96556 KB Execution killed with signal 11
17 Runtime error 110 ms 93120 KB Execution killed with signal 11