結果
問題 | No.897 compαctree |
ユーザー |
![]() |
提出日時 | 2019-10-04 21:22:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 7,219 bytes |
コンパイル時間 | 2,433 ms |
コンパイル使用メモリ | 192,432 KB |
最終ジャッジ日時 | 2025-01-07 20:18:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include<bits/stdc++.h>using namespace std;const int mod = 1012924417;using int64 = long long;const int64 infll = (1LL << 62) - 1;const int inf = (1 << 30) - 1;struct IoSetup {IoSetup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);cerr << fixed << setprecision(10);}} iosetup;template< typename T1, typename T2 >ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {os << p.first << " " << p.second;return os;}template< typename T1, typename T2 >istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second;return is;}template< typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template< typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in : v) is >> in;return is;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template< typename T = int64 >vector< T > make_v(size_t a) {return vector< T >(a);}template< typename T, typename... Ts >auto make_v(size_t a, Ts... ts) {return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));}template< typename T, typename V >typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {t = v;}template< typename T, typename V >typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {for(auto &e : t) fill_v(e, v);}template< typename F >struct FixPoint : F {FixPoint(F &&f) : F(forward< F >(f)) {}template< typename... Args >decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, forward< Args >(args)...);}};template< typename F >inline decltype(auto) MFP(F &&f) {return FixPoint< F >{forward< F >(f)};}template< typename Monoid = int, typename OperatorMonoid = Monoid >struct LinkCutTree {using F = function< Monoid(Monoid, Monoid) >;using G = function< Monoid(Monoid, OperatorMonoid, int) >;using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;using S = function< Monoid(Monoid) >;struct Node {Node *l, *r, *p;int idx;Monoid key, sum;OperatorMonoid lazy;bool rev;int sz;bool is_root() {return !p || (p->l != this && p->r != this);}Node(int idx, const Monoid &key, const OperatorMonoid &om) :idx(idx), key(key), sum(key), lazy(om), sz(1),l(nullptr), r(nullptr), p(nullptr), rev(false) {}};const Monoid M1;const OperatorMonoid OM0;const F f;const G g;const H h;const S s;LinkCutTree() : LinkCutTree([](Monoid a, Monoid b) { return a + b; }, [](Monoid a) { return a; }, Monoid()) {}LinkCutTree(const F &f, const S &s, const Monoid &M1) :LinkCutTree(f, G(), H(), s, M1, OperatorMonoid()) {}LinkCutTree(const F &f, const G &g, const H &h, const S &s,const Monoid &M1, const OperatorMonoid &OM0) :f(f), g(g), h(h), s(s), M1(M1), OM0(OM0) {}Node *make_node(int idx, const Monoid &v = Monoid()) {return new Node(idx, v, OM0);}void propagate(Node *t, const OperatorMonoid &x) {t->lazy = h(t->lazy, x);t->key = g(t->key, x, 1);t->sum = g(t->sum, x, t->sz);}void toggle(Node *t) {assert(t);swap(t->l, t->r);t->sum = s(t->sum);t->rev ^= true;}void push(Node *t) {if(t->lazy != OM0) {if(t->l) propagate(t->l, t->lazy);if(t->r) propagate(t->r, t->lazy);t->lazy = OM0;}if(t->rev) {if(t->l) toggle(t->l);if(t->r) toggle(t->r);t->rev = false;}}void update(Node *t) {t->sz = 1;t->sum = t->key;if(t->l) t->sz += t->l->sz, t->sum = f(t->l->sum, t->sum);if(t->r) t->sz += t->r->sz, t->sum = f(t->sum, t->r->sum);}void rotr(Node *t) {auto *x = t->p, *y = x->p;if((x->l = t->r)) t->r->p = x;t->r = x, x->p = t;update(x), update(t);if((t->p = y)) {if(y->l == x) y->l = t;if(y->r == x) y->r = t;update(y);}}void rotl(Node *t) {auto *x = t->p, *y = x->p;if((x->r = t->l)) t->l->p = x;t->l = x, x->p = t;update(x), update(t);if((t->p = y)) {if(y->l == x) y->l = t;if(y->r == x) y->r = t;update(y);}}void splay(Node *t) {push(t);while(!t->is_root()) {auto *q = t->p;if(q->is_root()) {push(q), push(t);if(q->l == t) rotr(t);else rotl(t);} else {auto *r = q->p;push(r), push(q), push(t);if(r->l == q) {if(q->l == t) rotr(q), rotr(t);else rotl(t), rotr(t);} else {if(q->r == t) rotl(q), rotl(t);else rotr(t), rotl(t);}}}}Node *expose(Node *t) {Node *rp = nullptr;for(Node *cur = t; cur; cur = cur->p) {splay(cur);cur->r = rp;update(cur);rp = cur;}splay(t);return rp;}void link(Node *child, Node *parent) {expose(child);expose(parent);child->p = parent;parent->r = child;update(parent);}void cut(Node *child) {expose(child);auto *parent = child->l;child->l = nullptr;parent->p = nullptr;update(child);}void evert(Node *t) {expose(t);toggle(t);push(t);}Node *lca(Node *u, Node *v) {if(get_root(u) != get_root(v)) return nullptr;expose(u);return expose(v);}vector< int > get_path(Node *x) {vector< int > vs;function< void(Node *) > dfs = [&](Node *cur) {if(!cur) return;push(cur);dfs(cur->r);vs.push_back(cur->idx);dfs(cur->l);};expose(x);dfs(x);return vs;}void set_propagate(Node *t, const OperatorMonoid &x) {expose(t);propagate(t, x);push(t);}Node *get_kth(Node *x, int k) {expose(x);while(x) {push(x);if(x->r && x->r->sz > k) {x = x->r;} else {if(x->r) k -= x->r->sz;if(k == 0) return x;k -= 1;x = x->l;}}return nullptr;}Node *get_root(Node *x) {expose(x);while(x->l) {push(x);x = x->l;}return x;}};int main() {/*int N;cin >> N;auto f = [](int a, int b) {return a;};auto g = [](int a, int b, int len) {return a;};auto h = [](int a, int b) {return a;};auto s = [](int a) {return a;};using LCT = LinkCutTree<>;LCT lct(f, g, h, s, 0, 0);vector< LCT::Node * > ver(N);for(int i = 0; i < N; i++) {ver[i] = lct.make_node(i);}*/int Q;cin >> Q;while(Q--) {int N, K;cin >> N >> K;if(K == 1) {cout << N - 1 << endl;continue;}int64 uku = 1, now = 1;int dep = 0;while(uku < N) {int64 nxt = now * K;now *= K;uku += nxt;dep += 1;}cout << dep << endl;}}