oj.uz

Submission #524121

# Submission time Handle Problem Language Result Execution time Memory
524121 2022-02-08T16:37:28 Z keertan Regions (IOI09_regions) C++17
50 / 100
 1931 ms 96632 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])>=700){
      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 14 ms 21960 KB Output is correct
3 Correct 15 ms 21960 KB Output is correct
4 Correct 17 ms 21960 KB Output is correct
5 Correct 21 ms 22088 KB Output is correct
6 Correct 32 ms 22248 KB Output is correct
7 Correct 44 ms 22216 KB Output is correct
8 Correct 48 ms 22336 KB Output is correct
9 Correct 65 ms 22976 KB Output is correct
10 Correct 106 ms 23232 KB Output is correct
11 Correct 161 ms 23736 KB Output is correct
12 Correct 138 ms 24480 KB Output is correct
13 Correct 242 ms 24384 KB Output is correct
14 Correct 232 ms 24992 KB Output is correct
15 Correct 311 ms 28404 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1153 ms 30632 KB Output isn't correct
2 Correct 1104 ms 29092 KB Output is correct
3 Incorrect 1783 ms 35748 KB Output isn't correct
4 Correct 307 ms 26036 KB Output is correct
5 Correct 358 ms 28452 KB Output is correct
6 Correct 555 ms 28260 KB Output is correct
7 Correct 867 ms 29292 KB Output is correct
8 Correct 941 ms 37872 KB Output is correct
9 Correct 1931 ms 43432 KB Output is correct
10 Runtime error 103 ms 82484 KB Execution killed with signal 11
11 Runtime error 112 ms 69204 KB Execution killed with signal 11
12 Runtime error 121 ms 73324 KB Execution killed with signal 11
13 Runtime error 122 ms 74152 KB Execution killed with signal 11
14 Runtime error 116 ms 72868 KB Execution killed with signal 11
15 Runtime error 114 ms 82540 KB Execution killed with signal 11
16 Runtime error 112 ms 96632 KB Execution killed with signal 11
17 Runtime error 112 ms 93144 KB Execution killed with signal 11