oj.uz

Submission #524172

# Submission time Handle Problem Language Result Execution time Memory
524172 2022-02-08T18:19:49 Z keertan Regions (IOI09_regions) C++17
60 / 100
 2220 ms 95684 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])>=512){
      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;
    if (sz(col[r])>=512){cout<<mp[{r,r1}]<<endl;continue;}
    else if (sz(col[r])<sz(col[r1])){
      cout<<parent(r,r1)<<endl;
    }
    else{
      cout<<child(r,r1)<<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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21960 KB Output is correct
2 Correct 12 ms 21960 KB Output is correct
3 Correct 13 ms 21960 KB Output is correct
4 Correct 15 ms 21960 KB Output is correct
5 Correct 16 ms 22072 KB Output is correct
6 Correct 20 ms 22088 KB Output is correct
7 Correct 40 ms 22088 KB Output is correct
8 Correct 46 ms 22216 KB Output is correct
9 Correct 58 ms 22604 KB Output is correct
10 Correct 84 ms 22728 KB Output is correct
11 Correct 138 ms 23112 KB Output is correct
12 Correct 150 ms 23624 KB Output is correct
13 Correct 175 ms 23372 KB Output is correct
14 Correct 174 ms 24112 KB Output is correct
15 Correct 320 ms 27236 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1412 ms 28480 KB Output is correct
2 Correct 1538 ms 27336 KB Output is correct
3 Correct 2220 ms 30848 KB Output is correct
4 Correct 261 ms 24264 KB Output is correct
5 Correct 308 ms 26184 KB Output is correct
6 Correct 999 ms 25952 KB Output is correct
7 Correct 1025 ms 27200 KB Output is correct
8 Correct 856 ms 33288 KB Output is correct
9 Correct 1938 ms 34216 KB Output is correct
10 Runtime error 125 ms 80776 KB Execution killed with signal 11
11 Runtime error 127 ms 66732 KB Execution killed with signal 11
12 Runtime error 118 ms 70904 KB Execution killed with signal 11
13 Runtime error 104 ms 71764 KB Execution killed with signal 11
14 Runtime error 117 ms 70432 KB Execution killed with signal 11
15 Runtime error 105 ms 80960 KB Execution killed with signal 11
16 Runtime error 116 ms 95684 KB Execution killed with signal 11
17 Runtime error 109 ms 91888 KB Execution killed with signal 11