oj.uz

Submission #559165

# Submission time Handle Problem Language Result Execution time Memory
559165 2022-05-09T12:56:38 Z loctildore Regions (IOI09_regions) C++14
45 / 100
 5734 ms 23784 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;
      }
      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_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 5 ms 6696 KB Output is correct
3 Correct 6 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 20 ms 6864 KB Output is correct
7 Correct 28 ms 6864 KB Output is correct
8 Correct 36 ms 6864 KB Output is correct
9 Correct 46 ms 7120 KB Output is correct
10 Correct 81 ms 7316 KB Output is correct
11 Correct 117 ms 7504 KB Output is correct
12 Correct 138 ms 7928 KB Output is correct
13 Correct 167 ms 7760 KB Output is correct
14 Correct 276 ms 8400 KB Output is correct
15 Correct 249 ms 10064 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2096 ms 11812 KB Output isn't correct
2 Incorrect 2607 ms 11376 KB Output isn't correct
3 Incorrect 2895 ms 13184 KB Output isn't correct
4 Correct 224 ms 8400 KB Output is correct
5 Correct 370 ms 9552 KB Output is correct
6 Incorrect 1105 ms 9776 KB Output isn't correct
7 Correct 1641 ms 10676 KB Output is correct
8 Incorrect 1375 ms 14300 KB Output isn't correct
9 Correct 2444 ms 15716 KB Output is correct
10 Correct 5734 ms 19232 KB Output is correct
11 Correct 5471 ms 16016 KB Output is correct
12 Incorrect 1534 ms 18180 KB Output isn't correct
13 Incorrect 1927 ms 18088 KB Output isn't correct
14 Incorrect 2719 ms 18524 KB Output isn't correct
15 Incorrect 3453 ms 21304 KB Output isn't correct
16 Incorrect 3289 ms 23784 KB Output isn't correct
17 Incorrect 2422 ms 23408 KB Output isn't correct