oj.uz

Submission #559195

# Submission time Handle Problem Language Result Execution time Memory
559195 2022-05-09T13:20:12 Z loctildore Regions (IOI09_regions) C++14
100 / 100
 3272 ms 29184 KB 
#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 51
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;
      }
      fatvals[i].push_back({INT_MIN,0});
      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_MAX)))->s;
      }
      cout<<ans<<endl;
      if (reg[b].size()>=cutoff) {
        um[(ll)a*25069+b]=ans;
      }
    }
  }
  return 0;
}

Compilation message

regions.cpp: In function 'int main()':
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++) {
      |                       ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6736 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 6 ms 6736 KB Output is correct
4 Correct 7 ms 6736 KB Output is correct
5 Correct 11 ms 6736 KB Output is correct
6 Correct 19 ms 6864 KB Output is correct
7 Correct 34 ms 6864 KB Output is correct
8 Correct 37 ms 6864 KB Output is correct
9 Correct 45 ms 7120 KB Output is correct
10 Correct 79 ms 7248 KB Output is correct
11 Correct 117 ms 8120 KB Output is correct
12 Correct 141 ms 8124 KB Output is correct
13 Correct 157 ms 9020 KB Output is correct
14 Correct 215 ms 9584 KB Output is correct
15 Correct 242 ms 11188 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 13416 KB Output is correct
2 Correct 1146 ms 12772 KB Output is correct
3 Correct 1693 ms 16648 KB Output is correct
4 Correct 179 ms 8836 KB Output is correct
5 Correct 321 ms 9868 KB Output is correct
6 Correct 313 ms 10104 KB Output is correct
7 Correct 901 ms 11392 KB Output is correct
8 Correct 978 ms 16428 KB Output is correct
9 Correct 1432 ms 20376 KB Output is correct
10 Correct 2730 ms 27596 KB Output is correct
11 Correct 3272 ms 25120 KB Output is correct
12 Correct 1734 ms 21600 KB Output is correct
13 Correct 1866 ms 22516 KB Output is correct
14 Correct 2804 ms 22668 KB Output is correct
15 Correct 3164 ms 28136 KB Output is correct
16 Correct 2468 ms 29184 KB Output is correct
17 Correct 2781 ms 28728 KB Output is correct