oj.uz

Submission #524165

# Submission time Handle Problem Language Result Execution time Memory
524165 2022-02-08T18:12:26 Z keertan Regions (IOI09_regions) C++17
24 / 100
 7326 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;}
    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 12 ms 21960 KB Output is correct
2 Correct 11 ms 21988 KB Output is correct
3 Correct 12 ms 21960 KB Output is correct
4 Correct 15 ms 21960 KB Output is correct
5 Correct 16 ms 22008 KB Output is correct
6 Correct 24 ms 22088 KB Output is correct
7 Correct 42 ms 22088 KB Output is correct
8 Correct 44 ms 22220 KB Output is correct
9 Correct 60 ms 22712 KB Output is correct
10 Correct 62 ms 22640 KB Output is correct
11 Correct 120 ms 23088 KB Output is correct
12 Correct 130 ms 23624 KB Output is correct
13 Correct 204 ms 23368 KB Output is correct
14 Correct 259 ms 24008 KB Output is correct
15 Incorrect 202 ms 27576 KB Output isn't correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2272 ms 29640 KB Time limit exceeded (wall clock)
2 Execution timed out 2923 ms 29508 KB Time limit exceeded (wall clock)
3 Execution timed out 7326 ms 35016 KB Time limit exceeded (wall clock)
4 Correct 212 ms 24244 KB Output is correct
5 Correct 301 ms 26184 KB Output is correct
6 Runtime error 841 ms 49216 KB Execution killed with signal 13
7 Execution timed out 935 ms 65464 KB Time limit exceeded (wall clock)
8 Execution timed out 1411 ms 96720 KB Time limit exceeded (wall clock)
9 Execution timed out 2464 ms 119132 KB Time limit exceeded (wall clock)
10 Runtime error 96 ms 80848 KB Execution killed with signal 11
11 Runtime error 105 ms 66744 KB Execution killed with signal 11
12 Runtime error 123 ms 70948 KB Execution killed with signal 11
13 Runtime error 104 ms 71744 KB Execution killed with signal 11
14 Runtime error 113 ms 70504 KB Execution killed with signal 11
15 Runtime error 102 ms 80960 KB Execution killed with signal 11
16 Runtime error 112 ms 95624 KB Execution killed with signal 11
17 Runtime error 128 ms 91840 KB Execution killed with signal 11