oj.uz

Submission #523983

# Submission time Handle Problem Language Result Execution time Memory
523983 2022-02-08T14:03:31 Z keertan Regions (IOI09_regions) C++17
0 / 100
 119 ms 95868 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;
  }
}
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 11 ms 19016 KB Unexpected end of file - int32 expected
2 Execution timed out 9 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 10 ms 19196 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 14 ms 19272 KB Time limit exceeded (wall clock)
8 Execution timed out 13 ms 19320 KB Time limit exceeded (wall clock)
9 Execution timed out 17 ms 19908 KB Time limit exceeded (wall clock)
10 Execution timed out 22 ms 19840 KB Time limit exceeded (wall clock)
11 Execution timed out 15 ms 20296 KB Time limit exceeded (wall clock)
12 Execution timed out 18 ms 20936 KB Time limit exceeded (wall clock)
13 Execution timed out 24 ms 20600 KB Time limit exceeded (wall clock)
14 Execution timed out 24 ms 21436 KB Time limit exceeded (wall clock)
15 Execution timed out 37 ms 25068 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 32 ms 25708 KB Time limit exceeded (wall clock)
2 Execution timed out 37 ms 24388 KB Time limit exceeded (wall clock)
3 Execution timed out 34 ms 28232 KB Time limit exceeded (wall clock)
4 Execution timed out 106 ms 22092 KB Time limit exceeded (wall clock)
5 Execution timed out 50 ms 23864 KB Time limit exceeded (wall clock)
6 Execution timed out 33 ms 23488 KB Time limit exceeded (wall clock)
7 Execution timed out 36 ms 24904 KB Time limit exceeded (wall clock)
8 Execution timed out 48 ms 31936 KB Time limit exceeded (wall clock)
9 Runtime error 91 ms 61644 KB Execution killed with signal 11
10 Runtime error 90 ms 75200 KB Execution killed with signal 11
11 Runtime error 98 ms 60224 KB Execution killed with signal 11
12 Runtime error 103 ms 63484 KB Execution killed with signal 11
13 Runtime error 103 ms 64380 KB Execution killed with signal 11
14 Runtime error 106 ms 63256 KB Execution killed with signal 11
15 Runtime error 96 ms 75488 KB Execution killed with signal 11
16 Runtime error 119 ms 95868 KB Execution killed with signal 11
17 Runtime error 106 ms 89516 KB Execution killed with signal 11