Submission #500744

#	Time	Username	Problem	Language	Result	Execution time	Memory
500744		cs142857	Regions (IOI09_regions)	C++17	100 / 100	2971 ms	29500 KiB

regions

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

#ifdef DBG
  #define dbg 1
  #define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
  #define Dps(...) Dbgs(__VA_ARGS__)
#else
  #define dbg 0
  #define dpf(...) 42
  #define Dps(...) 42
#endif
 
#define SIZE(c) int((c).size())
#define FOR(i,l,r) for(int i = (l); i < (r); ++i)
#define REP(i,c) for(auto &i : (c))
#define ALL(c) (c).begin(),(c).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;

template <typename T> inline bool UpdateMax(T& x, T v) {
  if(v > x) {x=v; return 1;} else return 0;
}
template <typename T> inline bool UpdateMin(T& x, T v) {
  if(v < x) {x=v; return 1;} else return 0;
}

template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;

inline namespace output {
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) {
  return os << "{" << v.first << " " << v.second << "}";
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "{";
  bool first = 1;
  REP(x, v) {
    if(first) first=0; else os << " ";
    os << x;
  }
  return os << "}";
}
}  // namespace output

inline namespace output {  // Only for debug now.
template <class T>
void PrSep(std::ostream& os, string, const T& t) { os << t; }
template <class T, class... U>
void PrSep(std::ostream& os, string sep, const T& t, const U&... u) {
  PrSep(os, sep, t); os << sep; PrSep(os, sep, u...);
}

// Print w/ spaces, end with newline
void Ps() { cout << "\n"; }
template<class ...T> void Ps(const T&... t) { PrSep(cout," ",t...); Ps(); } 
template<class ...T> void Dbgs(const T&... t) { PrSep(cerr," ",t...); cerr << endl; } 
}  // namespace output

int n, m;
VI par, home; 
VI r_cnt;
int big_cnt;

vector<char> rtype;
VI rtype_cnt;
vector<int> ridx;

vector<vector<PI>> r0_subtree_dfs_range;
vector<VI> dfs_pos;

vector<VI> ans10;
vector<vector<i64>> ans11;

void Build() {
  VI start(n, -1);
  VI next_son(n, -1);
  FOR(i, 1, n) {
    next_son[i] = start[par[i]];
    start[par[i]] = i;
  }

  ans10.assign(rtype_cnt[1], VI(rtype_cnt[0], 0));
  ans11.assign(rtype_cnt[1], vector<i64>(rtype_cnt[1], 0));

  r0_subtree_dfs_range.assign(rtype_cnt[0], {});
  dfs_pos.assign(m, {});
  FOR(i, 0, m) {
    if (rtype[i] == 0) r0_subtree_dfs_range[ridx[i]].reserve(r_cnt[i]);
    dfs_pos[i].reserve(r_cnt[i]);
  }

  VI par_r1cnt(rtype_cnt[1], 0);
  VI par_r1;
  int dfsn = -1;
  const std::function<void(int)> Dfs = [&](int u) {
    dfsn++;
    int ru = home[u];
    REP(p, par_r1) {
      if (rtype[ru] == 0) {
        ans10[ridx[p]][ridx[ru]] += par_r1cnt[ridx[p]];
      } else {
        ans11[ridx[p]][ridx[ru]] += par_r1cnt[ridx[p]];
      }
    }
    if (rtype[ru] == 1) {
      if (par_r1cnt[ridx[ru]]++ == 0) par_r1.pb(ru);
    }
    dfs_pos[ru].pb(dfsn);

    int dfs_l = dfsn + 1;
    for (int v = start[u]; v >= 0; v = next_son[v]) {
      Dfs(v);
    }

    if (rtype[ru] == 1) {
      if (--par_r1cnt[ridx[ru]] == 0) {
        assert(par_r1.back() == ru);
        par_r1.pop_back();
      }
    } else {
      r0_subtree_dfs_range[ridx[ru]].pb({dfs_l, dfsn});
    }
  };

  Dfs(0);
}

i64 Query(int rs, int rt) {
  if (rtype[rs] == 1) {
    if (rtype[rt] == 0) return ans10[ridx[rs]][ridx[rt]];
    return ans11[ridx[rs]][ridx[rt]];
  }

  i64 res = 0;
  REP(range, r0_subtree_dfs_range[ridx[rs]]) {
    const auto& pos = dfs_pos[rt];
    auto li = lower_bound(ALL(pos), range.first);
    auto ri = upper_bound(li, pos.end(), range.second);
    res += distance(li, ri);
  }
  return res;
}

void Solve() {
  int nq;
  scanf("%d%d%d",&n,&m,&nq);
  par.resize(n);
  home.resize(n);
  scanf("%d", &home[0]);
  --home[0];
  FOR(i, 1, n) {
    scanf("%d%d", &par[i], &home[i]);
    --par[i],--home[i];
  }

  big_cnt = round(sqrt(n));
  r_cnt.assign(n, 0);
  FOR(i, 0, n) ++r_cnt[home[i]];

  rtype.assign(m, 0);
  ridx.assign(m, -1);
  rtype_cnt.assign(2, 0);
  FOR(i, 0, m) {
    rtype[i] = r_cnt[i] > big_cnt;
    ridx[i] = rtype_cnt[rtype[i]]++;
  }

  Build();

  while (nq--) {
    int rs,rt;
    scanf("%d%d", &rs, &rt);
    --rs, --rt;
    printf("%lld\n", Query(rs, rt));
    fflush(stdout);
  }
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  for (int i = 1; i <= t; ++i) {
    // printf("Case #%d: ", i);
    Solve();
  }

  return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void Solve()':
regions.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |   scanf("%d%d%d",&n,&m,&nq);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:186:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |   scanf("%d", &home[0]);
      |   ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:189:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |     scanf("%d%d", &par[i], &home[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:209:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  209 |     scanf("%d%d", &rs, &rt);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85