Submission #559158

#	Time	Username	Problem	Language	Result	Execution time	Memory
559158		loctildore	Regions (IOI09_regions)	C++14	65 / 100	8083 ms	23148 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) begin(x), end(x)
#define cutoff INT_MIN
int n,r,q,s,a,b;
vector<int> chd[200069];
int nxt;
int h[200069];
vector<int> reg[25069],vals[25069];
vector<pair<int,int>> fatvals[25069];
int dfsord[200069],excl[200069];
unordered_map<ll,int> um;
void dfs(int x) {
  dfsord[x]=nxt;
  nxt++;
  for (auto i:chd[x]) {
    dfs(i);
  }
  excl[x]=nxt;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>r>>q;
  cin>>h[0];
  for (int i = 1; i < n; i++) {
    cin>>s>>h[i];
    s--;
    chd[s].push_back(i);
  }
  dfs(0);
  for (int i = 0; i < n; i++) {
    h[i]--;
    reg[h[i]].push_back(i);
    vals[h[i]].push_back(dfsord[i]);
  }
  for (int i = 0; i < 25069; i++) {
    sort(all(vals[i]));
    if (reg[i].size()>=cutoff) {
      vector<pair<int,int>> tmpfat;
      for (int j : reg[i]) {
        tmpfat.push_back({dfsord[j],1});
        tmpfat.push_back({excl[j],-1});
      }
      sort(all(tmpfat));
      for (int j = 1; j < tmpfat.size(); j++) {
        tmpfat[j].s+=tmpfat[j-1].s;
      }
      for (auto j:tmpfat) {
        if (fatvals[i].size()&&fatvals[i].rbegin()->f==j.f) {
          fatvals[i].pop_back();
        }
        fatvals[i].push_back(j);
      }
    }
  }
  for (int i = 0; i < q; i++) {
    cin>>a>>b;
    a--;b--;
    if (reg[a].size()<cutoff) {
      int ans=0;
      for (auto j:reg[a]) {
        ans+=lower_bound(all(vals[b]),excl[j])-lower_bound(all(vals[b]),dfsord[j]);
      }
      cout<<ans<<endl;
    }
    else {
      if (um.find((ll)a*25069+b)!=um.end()) {
        cout<<um[(ll)a*25069+b]<<endl;
        continue;
      }
      int ans=0;
      for (auto j:reg[b]) {
        ans+=lower_bound(all(fatvals[a]),make_pair(dfsord[j],INT_MIN))->s;
      }
      cout<<ans<<endl;
      if (reg[b].size()>=cutoff) {
        um[(ll)a*25069+b]=ans;
      }
    }
  }
  return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:43:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     if (reg[i].size()>=cutoff) {
      |                      ^
regions.cpp:50:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |       for (int j = 1; j < tmpfat.size(); j++) {
      |                       ~~^~~~~~~~~~~~~~~
regions.cpp:64:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     if (reg[a].size()<cutoff) {
      |                      ^
regions.cpp:81:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |       if (reg[b].size()>=cutoff) {
      |                        ^

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