oj.uz

Submission #524118

# Submission time Handle Problem Language Result Execution time Memory
524118 2022-02-08T16:34:05 Z keertan Regions (IOI09_regions) C++17
35 / 100
 2032 ms 96564 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 13 ms 21972 KB Output is correct
2 Correct 14 ms 21960 KB Output is correct
3 Correct 14 ms 22056 KB Output is correct
4 Correct 18 ms 22088 KB Output is correct
5 Correct 19 ms 22148 KB Output is correct
6 Correct 31 ms 22188 KB Output is correct
7 Correct 39 ms 22216 KB Output is correct
8 Correct 42 ms 22416 KB Output is correct
9 Correct 63 ms 23080 KB Output is correct
10 Correct 105 ms 23220 KB Output is correct
11 Correct 130 ms 23748 KB Output is correct
12 Correct 164 ms 24732 KB Output is correct
13 Correct 193 ms 24332 KB Output is correct
14 Correct 276 ms 25176 KB Output is correct
15 Correct 291 ms 28216 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1116 ms 31004 KB Output isn't correct
2 Correct 1303 ms 29148 KB Output is correct
3 Incorrect 2032 ms 35912 KB Output isn't correct
4 Correct 181 ms 26048 KB Output is correct
5 Correct 440 ms 28484 KB Output is correct
6 Incorrect 725 ms 30800 KB Output isn't correct
7 Incorrect 773 ms 30504 KB Output isn't correct
8 Incorrect 1575 ms 73728 KB Output isn't correct
9 Correct 1738 ms 43552 KB Output is correct
10 Runtime error 97 ms 82436 KB Execution killed with signal 11
11 Runtime error 113 ms 69276 KB Execution killed with signal 11
12 Runtime error 120 ms 73340 KB Execution killed with signal 11
13 Runtime error 105 ms 74048 KB Execution killed with signal 11
14 Runtime error 117 ms 72880 KB Execution killed with signal 11
15 Runtime error 108 ms 82556 KB Execution killed with signal 11
16 Runtime error 116 ms 96564 KB Execution killed with signal 11
17 Runtime error 125 ms 93180 KB Execution killed with signal 11