oj.uz

답안 #500744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500744 2022-01-01T06:53:03 Z cs142857 Regions (IOI09_regions) C++17
100 / 100
 2971 ms 29500 KB 
#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

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 3 ms 200 KB Output is correct
4 Correct 4 ms 200 KB Output is correct
5 Correct 6 ms 200 KB Output is correct
6 Correct 24 ms 272 KB Output is correct
7 Correct 32 ms 328 KB Output is correct
8 Correct 37 ms 272 KB Output is correct
9 Correct 39 ms 968 KB Output is correct
10 Correct 94 ms 584 KB Output is correct
11 Correct 127 ms 788 KB Output is correct
12 Correct 117 ms 1332 KB Output is correct
13 Correct 137 ms 1052 KB Output is correct
14 Correct 228 ms 1164 KB Output is correct
15 Correct 262 ms 5912 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1383 ms 3856 KB Output is correct
2 Correct 1276 ms 2656 KB Output is correct
3 Correct 2616 ms 6592 KB Output is correct
4 Correct 244 ms 1608 KB Output is correct
5 Correct 367 ms 4500 KB Output is correct
6 Correct 548 ms 4372 KB Output is correct
7 Correct 1052 ms 5512 KB Output is correct
8 Correct 1070 ms 15484 KB Output is correct
9 Correct 1701 ms 8252 KB Output is correct
10 Correct 2520 ms 27384 KB Output is correct
11 Correct 2971 ms 9024 KB Output is correct
12 Correct 855 ms 7696 KB Output is correct
13 Correct 1570 ms 9412 KB Output is correct
14 Correct 1751 ms 10392 KB Output is correct
15 Correct 2474 ms 16192 KB Output is correct
16 Correct 2403 ms 29500 KB Output is correct
17 Correct 2784 ms 27576 KB Output is correct