oj.uz

Submission #523980

# Submission time Handle Problem Language Result Execution time Memory
523980 2022-02-08T13:59:41 Z keertan Regions (IOI09_regions) C++17
0 / 100
 146 ms 95872 KB 
#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 = 2e5+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];
int stnd[N],ennd[N];
void dfs(int u,int v){
  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]){
    if (it==v){continue;}
    dfs(it,u);
  }
  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;
}
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()){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;
    fflush(stdout);
  }
}
int32_t main(){
  ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
  int tq = 1;
  //cin>>tq;
  for (;tq;tq--){solve();}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19016 KB Unexpected end of file - int32 expected
2 Execution timed out 8 ms 19016 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 19016 KB Time limit exceeded (wall clock)
4 Execution timed out 9 ms 19016 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 19144 KB Time limit exceeded (wall clock)
6 Execution timed out 12 ms 19144 KB Time limit exceeded (wall clock)
7 Execution timed out 12 ms 19188 KB Time limit exceeded (wall clock)
8 Execution timed out 17 ms 19272 KB Time limit exceeded (wall clock)
9 Execution timed out 17 ms 19808 KB Time limit exceeded (wall clock)
10 Execution timed out 16 ms 19868 KB Time limit exceeded (wall clock)
11 Execution timed out 13 ms 20296 KB Time limit exceeded (wall clock)
12 Execution timed out 17 ms 20960 KB Time limit exceeded (wall clock)
13 Execution timed out 23 ms 20684 KB Time limit exceeded (wall clock)
14 Execution timed out 30 ms 21312 KB Time limit exceeded (wall clock)
15 Execution timed out 34 ms 25036 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 30 ms 25692 KB Time limit exceeded (wall clock)
2 Execution timed out 44 ms 24336 KB Time limit exceeded (wall clock)
3 Execution timed out 32 ms 28208 KB Time limit exceeded (wall clock)
4 Execution timed out 117 ms 22316 KB Time limit exceeded (wall clock)
5 Execution timed out 44 ms 23880 KB Time limit exceeded (wall clock)
6 Execution timed out 40 ms 23356 KB Time limit exceeded (wall clock)
7 Execution timed out 36 ms 24868 KB Time limit exceeded (wall clock)
8 Execution timed out 49 ms 31996 KB Time limit exceeded (wall clock)
9 Runtime error 86 ms 61668 KB Execution killed with signal 11
10 Runtime error 103 ms 75268 KB Execution killed with signal 11
11 Runtime error 108 ms 60200 KB Execution killed with signal 11
12 Runtime error 133 ms 63504 KB Execution killed with signal 11
13 Runtime error 95 ms 64424 KB Execution killed with signal 11
14 Runtime error 130 ms 63224 KB Execution killed with signal 11
15 Runtime error 114 ms 75396 KB Execution killed with signal 11
16 Runtime error 131 ms 95872 KB Execution killed with signal 11
17 Runtime error 146 ms 89556 KB Execution killed with signal 11