oj.uz

Submission #524166

# Submission time Handle Problem Language Result Execution time Memory
524166 2022-02-08T18:13:17 Z keertan Regions (IOI09_regions) C++17
24 / 100
 2499 ms 119132 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 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])>=200){
      vector<int> ok(tmr+1);
      for (const int& it:col[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]-!!(euler[j]==i);
        }
      }
    }
  }
  for (int r,r1;q;q--){
    cin>>r>>r1;
    int ans=0;
    if (sz(col[r])>200){cout<<mp[{r,r1}]<<endl;}
    else if (sz(col[r])<sz(col[r1])){
      ans=parent(r,r1);
    }
    else{
     // cerr<<"fck\n";
      ans=child(r,r1);
    }
    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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21960 KB Output is correct
2 Correct 10 ms 21960 KB Output is correct
3 Correct 12 ms 21964 KB Output is correct
4 Correct 15 ms 21960 KB Output is correct
5 Correct 17 ms 21976 KB Output is correct
6 Correct 28 ms 22088 KB Output is correct
7 Correct 32 ms 22088 KB Output is correct
8 Correct 39 ms 22216 KB Output is correct
9 Correct 58 ms 22624 KB Output is correct
10 Correct 51 ms 22728 KB Output is correct
11 Correct 123 ms 23112 KB Output is correct
12 Correct 122 ms 23624 KB Output is correct
13 Correct 174 ms 23368 KB Output is correct
14 Correct 264 ms 24112 KB Output is correct
15 Runtime error 195 ms 27592 KB Execution killed with signal 13

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 603 ms 29612 KB Time limit exceeded (wall clock)
2 Execution timed out 894 ms 29468 KB Time limit exceeded (wall clock)
3 Execution timed out 2499 ms 35036 KB Time limit exceeded (wall clock)
4 Correct 252 ms 24248 KB Output is correct
5 Correct 340 ms 26056 KB Output is correct
6 Runtime error 456 ms 49308 KB Execution killed with signal 13
7 Execution timed out 869 ms 65460 KB Time limit exceeded (wall clock)
8 Execution timed out 1374 ms 96840 KB Time limit exceeded (wall clock)
9 Execution timed out 2396 ms 119132 KB Time limit exceeded (wall clock)
10 Runtime error 99 ms 80832 KB Execution killed with signal 11
11 Runtime error 108 ms 66692 KB Execution killed with signal 11
12 Runtime error 129 ms 70944 KB Execution killed with signal 11
13 Runtime error 108 ms 71744 KB Execution killed with signal 11
14 Runtime error 116 ms 70440 KB Execution killed with signal 11
15 Runtime error 107 ms 80960 KB Execution killed with signal 11
16 Runtime error 127 ms 95752 KB Execution killed with signal 11
17 Runtime error 112 ms 91864 KB Execution killed with signal 11