oj.uz

Submission #524158

# Submission time Handle Problem Language Result Execution time Memory
524158 2022-02-08T18:04:15 Z keertan Regions (IOI09_regions) C++17
35 / 100
 1872 ms 95680 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])>=500){
      vector<int> ok(tmr+1);
      for (const int& it:adj[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 (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();}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21960 KB Output is correct
2 Correct 11 ms 21960 KB Output is correct
3 Correct 13 ms 22056 KB Output is correct
4 Correct 15 ms 21992 KB Output is correct
5 Correct 19 ms 22112 KB Output is correct
6 Correct 27 ms 22220 KB Output is correct
7 Correct 42 ms 22208 KB Output is correct
8 Correct 31 ms 22336 KB Output is correct
9 Correct 62 ms 22908 KB Output is correct
10 Correct 54 ms 23260 KB Output is correct
11 Correct 118 ms 23620 KB Output is correct
12 Correct 147 ms 24448 KB Output is correct
13 Correct 189 ms 24228 KB Output is correct
14 Correct 255 ms 24832 KB Output is correct
15 Correct 287 ms 28128 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 966 ms 29620 KB Output isn't correct
2 Incorrect 1070 ms 28744 KB Output isn't correct
3 Incorrect 1872 ms 34120 KB Output isn't correct
4 Correct 242 ms 25752 KB Output is correct
5 Correct 347 ms 28348 KB Output is correct
6 Incorrect 684 ms 35244 KB Output isn't correct
7 Correct 804 ms 28712 KB Output is correct
8 Incorrect 984 ms 39232 KB Output isn't correct
9 Correct 1603 ms 42464 KB Output is correct
10 Runtime error 100 ms 80820 KB Execution killed with signal 11
11 Runtime error 106 ms 66736 KB Execution killed with signal 11
12 Runtime error 134 ms 70976 KB Execution killed with signal 11
13 Runtime error 104 ms 71744 KB Execution killed with signal 11
14 Runtime error 122 ms 70496 KB Execution killed with signal 11
15 Runtime error 108 ms 81000 KB Execution killed with signal 11
16 Runtime error 113 ms 95680 KB Execution killed with signal 11
17 Runtime error 121 ms 91876 KB Execution killed with signal 11