oj.uz

Submission #559121

# Submission time Handle Problem Language Result Execution time Memory
559121 2022-05-09T12:28:06 Z loctildore Regions (IOI09_regions) C++14
65 / 100
 8000 ms 23112 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_MAX
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 6860 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 7 ms 6736 KB Output is correct
4 Correct 7 ms 6736 KB Output is correct
5 Correct 14 ms 6736 KB Output is correct
6 Correct 21 ms 6864 KB Output is correct
7 Correct 35 ms 6864 KB Output is correct
8 Correct 32 ms 6864 KB Output is correct
9 Correct 36 ms 7120 KB Output is correct
10 Correct 72 ms 7248 KB Output is correct
11 Correct 150 ms 7616 KB Output is correct
12 Correct 115 ms 8016 KB Output is correct
13 Correct 174 ms 7760 KB Output is correct
14 Correct 256 ms 8400 KB Output is correct
15 Correct 262 ms 10064 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8074 ms 11088 KB Time limit exceeded
2 Execution timed out 8048 ms 10184 KB Time limit exceeded
3 Execution timed out 8071 ms 12488 KB Time limit exceeded
4 Correct 253 ms 8400 KB Output is correct
5 Correct 343 ms 9556 KB Output is correct
6 Correct 1246 ms 9552 KB Output is correct
7 Correct 1492 ms 10644 KB Output is correct
8 Correct 1305 ms 14248 KB Output is correct
9 Correct 2191 ms 15796 KB Output is correct
10 Correct 3700 ms 19172 KB Output is correct
11 Correct 3860 ms 16020 KB Output is correct
12 Correct 6210 ms 17248 KB Output is correct
13 Correct 6688 ms 17368 KB Output is correct
14 Execution timed out 8021 ms 17264 KB Time limit exceeded
15 Execution timed out 8061 ms 20328 KB Time limit exceeded
16 Execution timed out 8032 ms 23112 KB Time limit exceeded
17 Execution timed out 8013 ms 22392 KB Time limit exceeded