제출 #559116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559116		loctildore	Regions (IOI09_regions)	C++14	45 / 100	4254 ms	23776 KiB

regions

#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_MAX))->s;
      }
      cout<<ans<<endl;
      if (reg[b].size()>=cutoff) {
        um[(ll)a*25069+b]=ans;
      }
    }
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 30 / 85