Submission #933063

#	Time	Username	Problem	Language	Result	Execution time	Memory
933063		vjudge1	Regions (IOI09_regions)	C++17	0 / 100	1459 ms	131072 KiB

regions

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) ;
using lli=long long int;
 
 
#ifndef LOCAL
    #define endl '\n'
#endif
 
vector<lli> ch;
lli aux=0;
vector<vector<lli>> sons;
vector<pair<lli,lli>> ranges;
void dfs(lli n){
  ch[n]=aux;
  lli ini=aux;
  aux++;
  for(lli x: sons[n]){
    dfs(x);
  }
  ranges[n]={ini, aux-1};
}
 vector<vector<lli>> ans;
 vector<lli> regions;
void solvefirstcase(lli n, vector<lli> &act){
  for(lli i=0; i<act.size(); ++i){
    ans[i][regions[n]]+=act[i];
  }
  act[regions[n]]++;
  for(lli x: sons[n]){
    solvefirstcase(x,act );
  }
  act[regions[n]]--;
}

struct segtree{
  segtree *left, *right;
  multiset<lli> values;
  lli l,r;
  segtree(lli a, lli b): l(a), r(b){
    lli m=(l+r)/2;
    if(l!=r){
      left=new segtree(l, m);
      right=new segtree(m+1, r);
    }
  }
  void insert(lli a, lli b, lli v){
    if(a<=l && r<=b){
      values.insert(v);
      return;
    }
    if(r<=a || b<=l){
      return;
    }
    left->insert(a,b,v);
    right->insert(a,b,v);
  }
  lli query(lli x, lli v){
    lli ans=values.count(v);
    if(l==r){
      return ans;
    }
    lli m=(l+r)/2;
    if(x<=m){
      ans+=left->query(x,v);
    }
    else{
      ans+=right->query(x,v);
    }
    return ans;
  }
};


void solve(){
    lli n,r,k;
    cin>>n>>r>>k;
    regions.resize(n);
    cin>>regions[0];
    regions[0]--;
    sons.resize(n);
    vector<vector<lli>> members(r);
    members[regions[0]].pb(0);
    for(lli i=1; i<n; ++i){
      deb(i);
      lli s;
      cin>>s>>regions[i];
      s--;
      regions[i]--;
      deb("hi");
      members[regions[i]].pb(i);
      deb("Hi2");
      sons[s].pb(i);
      deb("HI3");
    }
    ch.resize(n);
    ranges.resize(n);
    deb("hi");
 //   dfs(0);
    deb("hi");
    
      ans.resize(r, vector<lli> (r,0));
      vector<lli> act (r,0);
      solvefirstcase(0, act);
      for(lli i=0; i<k; ++i){
        lli a,b;
        cin>>a>>b;
        a--;
        b--;
        cout<<ans[a][b]<<endl;
      }
    
    /*
    else{
      segtree tree(0, n);
      for(lli i=0; i<n; ++i){
        tree.insert(ranges[i].first, ranges[i].second, regions[i]);
      }
      for(lli i=0; i<k; ++i){
        lli a,b;
        cin>>a>>b;
        a--;
        b--;
        lli ans=0;
        for(lli x: members[b]){
          ans+=tree.query(x, a);
        }
        cout<<ans<<endl;
      }
    }
    */
}
 
 
int main(){
  ios::ios_base::sync_with_stdio(0);
  cin.tie(0);
  #ifdef LOCAL
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
  #endif
  lli t=1;
// cin>>t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

regions.cpp: In function 'void solvefirstcase(lli, std::vector<long long int>&)':
regions.cpp:28:17: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(lli i=0; i<act.size(); ++i){
      |                ~^~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85