oj.uz

Submission #524156

# Submission time Handle Problem Language Result Execution time Memory
524156 2022-02-08T17:59:16 Z keertan Regions (IOI09_regions) C++17
35 / 100
 1880 ms 95812 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];
        }
      }
    }
  }
  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 11 ms 22044 KB Output is correct
2 Correct 11 ms 21960 KB Output is correct
3 Correct 14 ms 22056 KB Output is correct
4 Correct 17 ms 21960 KB Output is correct
5 Correct 15 ms 22100 KB Output is correct
6 Correct 27 ms 22204 KB Output is correct
7 Correct 36 ms 22216 KB Output is correct
8 Correct 27 ms 22372 KB Output is correct
9 Correct 58 ms 22864 KB Output is correct
10 Correct 107 ms 23184 KB Output is correct
11 Correct 94 ms 23632 KB Output is correct
12 Correct 161 ms 24360 KB Output is correct
13 Correct 180 ms 24216 KB Output is correct
14 Correct 262 ms 24708 KB Output is correct
15 Correct 286 ms 28024 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1069 ms 29620 KB Output isn't correct
2 Incorrect 938 ms 28456 KB Output isn't correct
3 Incorrect 1814 ms 34184 KB Output isn't correct
4 Correct 255 ms 25892 KB Output is correct
5 Correct 255 ms 28476 KB Output is correct
6 Incorrect 743 ms 35100 KB Output isn't correct
7 Correct 888 ms 28580 KB Output is correct
8 Incorrect 1037 ms 39252 KB Output isn't correct
9 Correct 1880 ms 42332 KB Output is correct
10 Runtime error 95 ms 80836 KB Execution killed with signal 11
11 Runtime error 108 ms 66744 KB Execution killed with signal 11
12 Runtime error 118 ms 71020 KB Execution killed with signal 11
13 Runtime error 104 ms 71744 KB Execution killed with signal 11
14 Runtime error 114 ms 70496 KB Execution killed with signal 11
15 Runtime error 109 ms 80932 KB Execution killed with signal 11
16 Runtime error 117 ms 95812 KB Execution killed with signal 11
17 Runtime error 118 ms 91840 KB Execution killed with signal 11