oj.uz

Submission #559158

# Submission time Handle Problem Language Result Execution time Memory
559158 2022-05-09T12:51:25 Z loctildore Regions (IOI09_regions) C++14
65 / 100
 8000 ms 23148 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 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

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.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 9 ms 6736 KB Output is correct
5 Correct 12 ms 6736 KB Output is correct
6 Correct 22 ms 6864 KB Output is correct
7 Correct 29 ms 6864 KB Output is correct
8 Correct 32 ms 6864 KB Output is correct
9 Correct 47 ms 7120 KB Output is correct
10 Correct 79 ms 7248 KB Output is correct
11 Correct 110 ms 7504 KB Output is correct
12 Correct 132 ms 8016 KB Output is correct
13 Correct 167 ms 7760 KB Output is correct
14 Correct 272 ms 8528 KB Output is correct
15 Correct 258 ms 10088 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8010 ms 11080 KB Time limit exceeded
2 Execution timed out 8064 ms 10256 KB Time limit exceeded
3 Execution timed out 8061 ms 12488 KB Time limit exceeded
4 Correct 238 ms 8420 KB Output is correct
5 Correct 383 ms 9520 KB Output is correct
6 Correct 1515 ms 9680 KB Output is correct
7 Correct 1625 ms 10660 KB Output is correct
8 Correct 1085 ms 14316 KB Output is correct
9 Correct 2103 ms 15820 KB Output is correct
10 Correct 4242 ms 19272 KB Output is correct
11 Correct 4026 ms 16016 KB Output is correct
12 Correct 6267 ms 17252 KB Output is correct
13 Correct 6763 ms 17248 KB Output is correct
14 Execution timed out 8016 ms 17224 KB Time limit exceeded
15 Execution timed out 8083 ms 20352 KB Time limit exceeded
16 Execution timed out 8063 ms 23148 KB Time limit exceeded
17 Execution timed out 8067 ms 22432 KB Time limit exceeded