oj.uz

Submission #524122

# Submission time Handle Problem Language Result Execution time Memory
524122 2022-02-08T16:38:18 Z keertan Regions (IOI09_regions) C++17
50 / 100
 2001 ms 96580 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])>=1000){
      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 21960 KB Output is correct
2 Correct 16 ms 21968 KB Output is correct
3 Correct 18 ms 22068 KB Output is correct
4 Correct 20 ms 22076 KB Output is correct
5 Correct 21 ms 22072 KB Output is correct
6 Correct 34 ms 22288 KB Output is correct
7 Correct 34 ms 22376 KB Output is correct
8 Correct 46 ms 22412 KB Output is correct
9 Correct 68 ms 22976 KB Output is correct
10 Correct 106 ms 23224 KB Output is correct
11 Correct 130 ms 23644 KB Output is correct
12 Correct 147 ms 24592 KB Output is correct
13 Correct 177 ms 24364 KB Output is correct
14 Correct 158 ms 25072 KB Output is correct
15 Correct 288 ms 28256 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1121 ms 30724 KB Output isn't correct
2 Correct 1366 ms 28924 KB Output is correct
3 Incorrect 1954 ms 35808 KB Output isn't correct
4 Correct 282 ms 26144 KB Output is correct
5 Correct 218 ms 28420 KB Output is correct
6 Correct 548 ms 28220 KB Output is correct
7 Correct 645 ms 29060 KB Output is correct
8 Correct 788 ms 37928 KB Output is correct
9 Correct 2001 ms 43488 KB Output is correct
10 Runtime error 99 ms 82496 KB Execution killed with signal 11
11 Runtime error 121 ms 69312 KB Execution killed with signal 11
12 Runtime error 123 ms 73408 KB Execution killed with signal 11
13 Runtime error 106 ms 74048 KB Execution killed with signal 11
14 Runtime error 117 ms 72876 KB Execution killed with signal 11
15 Runtime error 114 ms 82600 KB Execution killed with signal 11
16 Runtime error 135 ms 96580 KB Execution killed with signal 11
17 Runtime error 110 ms 93216 KB Execution killed with signal 11