oj.uz

Submission #523993

# Submission time Handle Problem Language Result Execution time Memory
523993 2022-02-08T14:11:52 Z keertan Regions (IOI09_regions) C++17
3 / 100
 4067 ms 68236 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];
void dfs(int u,int v){
  tin[u]=tmr;
  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;
  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;
      }
    }
    ans+=cur-cur1;
  }
  return ans;
}
int parent(int p,int chld){
  int ans=0;
  for (const int& it:col[p]){
    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;
      }
    }
      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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 28488 KB Output isn't correct
2 Incorrect 17 ms 28452 KB Output isn't correct
3 Incorrect 17 ms 28488 KB Output isn't correct
4 Incorrect 21 ms 28488 KB Output isn't correct
5 Incorrect 21 ms 28572 KB Output isn't correct
6 Correct 39 ms 28652 KB Output is correct
7 Incorrect 42 ms 28664 KB Output isn't correct
8 Incorrect 54 ms 28736 KB Output isn't correct
9 Correct 80 ms 29496 KB Output is correct
10 Incorrect 127 ms 29516 KB Output isn't correct
11 Incorrect 148 ms 29872 KB Output isn't correct
12 Incorrect 175 ms 30732 KB Output isn't correct
13 Incorrect 217 ms 30464 KB Output isn't correct
14 Incorrect 245 ms 31032 KB Output isn't correct
15 Correct 316 ms 35048 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1058 ms 35684 KB Output isn't correct
2 Incorrect 1044 ms 34180 KB Output isn't correct
3 Incorrect 1974 ms 40336 KB Output isn't correct
4 Incorrect 276 ms 31996 KB Output isn't correct
5 Incorrect 397 ms 34964 KB Output isn't correct
6 Incorrect 571 ms 33996 KB Output isn't correct
7 Incorrect 877 ms 34428 KB Output isn't correct
8 Incorrect 1035 ms 44368 KB Output isn't correct
9 Incorrect 2040 ms 47904 KB Output isn't correct
10 Incorrect 4067 ms 57176 KB Output isn't correct
11 Incorrect 3676 ms 51180 KB Output isn't correct
12 Incorrect 1444 ms 45508 KB Output isn't correct
13 Incorrect 1838 ms 48344 KB Output isn't correct
14 Incorrect 2098 ms 49440 KB Output isn't correct
15 Incorrect 3116 ms 58668 KB Output isn't correct
16 Incorrect 3149 ms 68236 KB Output isn't correct
17 Incorrect 2849 ms 65716 KB Output isn't correct