oj.uz

Submission #524154

# Submission time Handle Problem Language Result Execution time Memory
524154 2022-02-08T17:55:45 Z keertan Regions (IOI09_regions) C++17
3 / 100
 3828 ms 79960 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target ("sse4.2")
#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 int 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];
map<pair<int,int>,int> mp;
int euler[N];
void dfs(int u){
  tin[u]=tmr;
  euler[tmr]=c[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;
  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);
  for (int i=1;i<=r;i++){
    if (sz(col[i])>=500){
      vector<int> ok(tmr+1);
      for (const int& it:adj[i]){
        ok[tin[it]]++;
        ok[tout[it]]--;
      }
      for (int j=1;j<tmr;j++){
        ok[j]+=ok[j-1];
        if (euler[j]){
          mp[{i,euler[j]}]+=ok[j];
        }
      }
    }
  }
  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:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 21980 KB Output isn't correct
2 Incorrect 12 ms 22028 KB Output isn't correct
3 Incorrect 14 ms 21960 KB Output isn't correct
4 Incorrect 16 ms 22068 KB Output isn't correct
5 Incorrect 21 ms 22092 KB Output isn't correct
6 Correct 34 ms 22184 KB Output is correct
7 Incorrect 41 ms 22196 KB Output isn't correct
8 Incorrect 43 ms 22340 KB Output isn't correct
9 Correct 62 ms 22976 KB Output is correct
10 Incorrect 99 ms 23136 KB Output isn't correct
11 Incorrect 146 ms 23704 KB Output isn't correct
12 Incorrect 145 ms 24248 KB Output isn't correct
13 Incorrect 213 ms 24220 KB Output isn't correct
14 Incorrect 235 ms 24636 KB Output isn't correct
15 Correct 281 ms 28164 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 957 ms 29324 KB Output isn't correct
2 Incorrect 1272 ms 28260 KB Output isn't correct
3 Incorrect 1962 ms 33856 KB Output isn't correct
4 Incorrect 232 ms 25584 KB Output isn't correct
5 Incorrect 384 ms 28368 KB Output isn't correct
6 Incorrect 671 ms 34932 KB Output isn't correct
7 Incorrect 841 ms 28180 KB Output isn't correct
8 Incorrect 1030 ms 39156 KB Output isn't correct
9 Incorrect 1571 ms 41860 KB Output isn't correct
10 Incorrect 3191 ms 49968 KB Output isn't correct
11 Incorrect 3508 ms 45692 KB Output isn't correct
12 Incorrect 1213 ms 40244 KB Output isn't correct
13 Incorrect 1649 ms 42512 KB Output isn't correct
14 Incorrect 2719 ms 64908 KB Output isn't correct
15 Incorrect 3538 ms 52968 KB Output isn't correct
16 Incorrect 3828 ms 60000 KB Output isn't correct
17 Incorrect 3540 ms 79960 KB Output isn't correct