oj.uz

Submission #559116

# Submission time Handle Problem Language Result Execution time Memory
559116 2022-05-09T12:20:48 Z loctildore Regions (IOI09_regions) C++14
45 / 100
 4254 ms 23776 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 500
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) {
      for (int j : reg[i]) {
        fatvals[i].push_back({dfsord[j],1});
        fatvals[i].push_back({excl[j],-1});
      }
      sort(all(fatvals[i]));
      for (int j = 1; j < fatvals[i].size(); j++) {
        fatvals[i][j].s+=fatvals[i][j-1].s;
      }
    }
  }
  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:49: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]
   49 |       for (int j = 1; j < fatvals[i].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 3 ms 6736 KB Output is correct
3 Correct 4 ms 6692 KB Output is correct
4 Correct 9 ms 6736 KB Output is correct
5 Correct 10 ms 6736 KB Output is correct
6 Correct 18 ms 6864 KB Output is correct
7 Correct 19 ms 6864 KB Output is correct
8 Correct 31 ms 6864 KB Output is correct
9 Correct 49 ms 7120 KB Output is correct
10 Correct 86 ms 7248 KB Output is correct
11 Correct 120 ms 7504 KB Output is correct
12 Correct 92 ms 7920 KB Output is correct
13 Correct 176 ms 7760 KB Output is correct
14 Correct 284 ms 8348 KB Output is correct
15 Correct 255 ms 10064 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2019 ms 11940 KB Output isn't correct
2 Incorrect 2669 ms 11044 KB Output isn't correct
3 Incorrect 3325 ms 13244 KB Output isn't correct
4 Correct 280 ms 8396 KB Output is correct
5 Correct 387 ms 9552 KB Output is correct
6 Incorrect 1063 ms 9772 KB Output isn't correct
7 Correct 1446 ms 10688 KB Output is correct
8 Incorrect 1298 ms 14344 KB Output isn't correct
9 Correct 2384 ms 15816 KB Output is correct
10 Correct 4238 ms 19276 KB Output is correct
11 Correct 4254 ms 16020 KB Output is correct
12 Incorrect 1320 ms 17992 KB Output isn't correct
13 Incorrect 1915 ms 17892 KB Output isn't correct
14 Incorrect 2207 ms 18404 KB Output isn't correct
15 Incorrect 3149 ms 21488 KB Output isn't correct
16 Incorrect 2573 ms 23752 KB Output isn't correct
17 Incorrect 2683 ms 23776 KB Output isn't correct