oj.uz

Submission #559152

# Submission time Handle Problem Language Result Execution time Memory
559152 2022-05-09T12:49:07 Z loctildore Regions (IOI09_regions) C++14
45 / 100
 4637 ms 23788 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) {
      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

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 5 ms 6736 KB Output is correct
4 Correct 7 ms 6736 KB Output is correct
5 Correct 10 ms 6736 KB Output is correct
6 Correct 21 ms 6864 KB Output is correct
7 Correct 28 ms 6864 KB Output is correct
8 Correct 41 ms 6864 KB Output is correct
9 Correct 62 ms 7120 KB Output is correct
10 Correct 51 ms 7248 KB Output is correct
11 Correct 117 ms 7504 KB Output is correct
12 Correct 139 ms 8008 KB Output is correct
13 Correct 187 ms 7760 KB Output is correct
14 Correct 290 ms 8304 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 2366 ms 11792 KB Output isn't correct
2 Incorrect 2742 ms 11368 KB Output isn't correct
3 Incorrect 3333 ms 13156 KB Output isn't correct
4 Correct 258 ms 8388 KB Output is correct
5 Correct 363 ms 9552 KB Output is correct
6 Incorrect 1014 ms 9780 KB Output isn't correct
7 Correct 1589 ms 10584 KB Output is correct
8 Incorrect 1254 ms 14312 KB Output isn't correct
9 Correct 2428 ms 15796 KB Output is correct
10 Correct 4637 ms 19292 KB Output is correct
11 Correct 4342 ms 16016 KB Output is correct
12 Incorrect 1458 ms 18280 KB Output isn't correct
13 Incorrect 1688 ms 18100 KB Output isn't correct
14 Incorrect 2277 ms 18524 KB Output isn't correct
15 Incorrect 3143 ms 21300 KB Output isn't correct
16 Incorrect 2769 ms 23788 KB Output isn't correct
17 Incorrect 2794 ms 23412 KB Output isn't correct