oj.uz

답안 #559131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559131 2022-05-09T12:32:34 Z loctildore Regions (IOI09_regions) C++14
45 / 100
 4472 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_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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 6712 KB Output is correct
5 Correct 10 ms 6736 KB Output is correct
6 Correct 19 ms 6864 KB Output is correct
7 Correct 25 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 76 ms 7248 KB Output is correct
11 Correct 115 ms 7504 KB Output is correct
12 Correct 87 ms 8016 KB Output is correct
13 Correct 155 ms 7760 KB Output is correct
14 Correct 282 ms 8400 KB Output is correct
15 Correct 175 ms 10064 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1996 ms 11940 KB Output isn't correct
2 Incorrect 2629 ms 11052 KB Output isn't correct
3 Incorrect 3145 ms 13248 KB Output isn't correct
4 Correct 235 ms 8400 KB Output is correct
5 Correct 258 ms 9552 KB Output is correct
6 Incorrect 1169 ms 9768 KB Output isn't correct
7 Correct 1579 ms 10704 KB Output is correct
8 Incorrect 1158 ms 14280 KB Output isn't correct
9 Correct 2094 ms 15708 KB Output is correct
10 Correct 3891 ms 19208 KB Output is correct
11 Correct 4472 ms 16024 KB Output is correct
12 Incorrect 1615 ms 18016 KB Output isn't correct
13 Incorrect 1876 ms 17884 KB Output isn't correct
14 Incorrect 2208 ms 18368 KB Output isn't correct
15 Incorrect 3518 ms 21340 KB Output isn't correct
16 Incorrect 2948 ms 23696 KB Output isn't correct
17 Incorrect 2808 ms 23776 KB Output isn't correct