Submission #493569

#	Time	Username	Problem	Language	Result	Execution time	Memory
493569		AndreyPavlov	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	383 ms	46004 KiB

ballmachine

/* Includes */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* Using libraries */
using namespace std;
using namespace __gnu_pbds;

/* Some libraries utils */
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/* Defines */
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define ld long double
#define vc vector
#define pb push_back
#define out(a) for (int i: a) cout << i << ' ';
#define graph(n, g) for (int i = 0; i < n; ++i) {int u, v; cin >> u >> v; --u; --v; g[u].push_back(v); g[v].push_back(u);}
#define eb emplace_back
#define pii pair <int, int>
#define sz(a) (int) a.size()
#define forn(i, n) for(int i = 0; i < n; ++i)

/* Constants */

const int inf = 1e15 + 7, mod = 1e9 + 7, maxn = 305, maxc = 27;

/* Utils */

class Utils {
public:
    class Modular {
    private:
        int n, md;
    public:
        Modular (): n(0), md(mod){}
        Modular (int n): md(mod) {
            this->n = normalize(n);
        }
        Modular (int n, int md): md(md) {
            this->n = normalize(n);
        }
        int normalize (int x) {
            if (abs(x) >= md) x %= md;
            if (x < 0) return x + md;
            return x;
        }
        Modular& operator = (int &x) {
            this->n = normalize(x);
            return *this;
        }
        Modular& operator += (const Modular &b) {return *this = *this + b;}
        Modular& operator -= (const Modular &b) {return *this = *this - b;}
        Modular& operator *= (const Modular &b) {return *this = *this * b;}
        Modular& operator /= (const Modular &b) {return *this = *this / b;}
        friend const Modular operator + (const Modular &a, const Modular &b) {
            assert(a & b);
            return Modular(a.n + b.n, a.md);
        }
        friend const Modular operator - (const Modular &a, const Modular &b) {
            assert(a & b);
            return Modular(a.n - b.n, a.md);
        }
        friend const Modular operator * (const Modular &a, const Modular &b) {
            assert(a & b);
            return Modular(a.n * b.n, a.md);
        }
        friend const Modular operator / (const Modular &a, const Modular &b) {
            assert(a & b);
            return Modular(a.n * Utils::Numbers::inverse(b.n, b.md), a.md);
        }
        friend ostream& operator << (ostream &os, const Modular& b) {
            return os << b.n;
        }
        friend istream& operator >> (istream &os, Modular& b) {
            os >> b.n;
            b = Modular(b.n, b.md);
            return os;
        }
        bool operator == (const Modular &b) const {
            return n == b.n;
        }
        bool operator != (const Modular &b) const {
            return !(*this == b);
        }
        friend bool operator & (const Modular &a, const Modular &b) {
            return a.md == b.md;
        }
    };
    class Numbers {
    public:
        using mint = Utils::Modular;
        int static gcd (int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }
        int static lcm (int a, int b) {
            if (a == 0 && b == 0) return 0;
            return a / Utils::Numbers::gcd(a, b) * b;
        }
        int static gcdex (int a, int b, int &x, int &y) {
            if (b == 0) {
                x = 1; y = 0;
                return a;
            }
            int x1, y1;
            int d = gcdex(b, a % b, x1, y1);
            x = y1;
            y = x1 - (a / b) * y1;
            return d;
        }
        int static inverse (int a, int m) {
            int x, y;
            int g = Utils::Numbers::gcdex(a, m, x, y);
            assert(g == 1);
            return (x % m + m) % m;
        }
        mint static bin_pow (mint a, int b, int m) {
            mint res(1, m);
            while (b) {
                if (b & 1)
                    res *= a;
                a *= a;
                b >>= 1;
            }
            return res;
        }
        int static bin_pow (int a, int b, int m) {
            int res = 1;
            while (b) {
                if (b & 1)
                    res = res * a % m;
                a = a * a % m;
                b >>= 1;
            }
            return res;
        }
        int static g (int n) {
            return n ^ (n >> 1);
        }
        int static rev_g (int n) {
            int f = 0;
            for (; n; n >>= 1) f ^= n;
            return f;
        }
        int static phi (int n) {
            int f = n;
            for (int i = 2; i * i <= n; ++i) {
                if (n % i == 0) {
                    while (n % i == 0) n /= i;
                    f -= f / i;
                }
            }
            if (n > 1) f -= f / n;
            return f;
        }
    };
    class Combinatoric {
    public:
        using mint = Utils::Modular;
        int maxn, mod;
        vc <mint> fact, inv;
        Combinatoric(int maxn, int mod = 1e9 + 7): maxn(maxn), mod(mod) {
            fact.resize(maxn + 1, mint(0, mod));
            inv.resize(maxn + 1, mint(0, mod));
            fact[0] = fact[1] = mint(1, mod);
            for (int i = 2; i <= maxn; ++i) {
                fact[i] = fact[i - 1] * mint(i, mod);
            }
            inv[maxn] = mint(1, mod) / fact[maxn];
            for (int i = maxn; i >= 1; --i) {
                inv[i - 1] = inv[i] * mint(i, mod);
            }
        }
        mint C (int n, int k) {
            if (k > n) return 1;
            return fact[n] * inv[n - k] * inv[k];
        }
        mint F (int n) {
            return fact[n];
        }
        mint InvF (int n) {
            return inv[n];
        }
    };
    class bitset {
    private:
        using T = unsigned long long;
        T SZ = 6;
        T base = 1ll << SZ;
        T mod = base - 1;
        T n;
    public:
        vc <T> t;
        bitset (T n) {
            this->n = n;
            t.resize((n + base - 1) / base);
        }
        T operator [](T i) {
            return t[i >> SZ] & (1 << (i & mod));
        }
        void set (T i, T val) {
            if ((*this)[i] == val) return;
            t[i >> SZ] ^= 1 << (i & mod);
        }
    };
    class Geometric {
    public:
        /* Point (and vector) */
        class pt {
        public:
            ld x, y;
            int i = -1;
            pt (ld x = 0, ld y = 0, int i = -1): x(x), y(y), i(i){}
            pt operator - () const {return pt(-x, -y);}
            pt operator + (pt &b) const {return pt(x + b.x, y + b.y);}
            pt operator - (pt &b) const {return pt(x - b.x, y - b.y);}
            pt& operator = (pt &b) {this->x = b.x, this->y = b.y;}
            ld operator * (pt &b) const {return x * b.x + y * b.y;}
            ld operator ^ (pt &b) const {return x * b.y - b.x * y;}
            bool operator == (pt &b) const {return x == b.x && y == b.y;}
            bool operator != (pt &b) const {return !(*this == b);}
            bool operator < (pt &b) const {return x == b.x ? y < b.y : x < b.x;}
            bool operator <= (pt &b) const {return *this < b || *this == b;}
            bool operator > (pt &b) const {return !(*this <= b);}
            bool operator >= (pt &b) const {return *this > b || *this == b;}
            friend ostream& operator << (ostream &os, pt &a) {return os << a.x << ' ' << a.y;}
            friend istream& operator >> (istream &os, pt &a) {return os >> a.x >> a.y;}
            ld operator [](int j) {return j == 0 ? x : y;}
            ld angle () {
                if (x == 0 && y == 0) return -1;
                if (x == 0)
                    return y > 0 ? 90 : 270;
                ld t = atan(y / x) * (360 );
                if (x > 0)
                    return y >= 0 ? t : t + 360;
                return t + 180;
            }
            ld len_sq () {return x * x + y * y;}
            ld length () {return sqrtl(this->len_sq());}
        };
        using pt = Utils::Geometric::pt;
        ld orientation (pt a, pt b, pt c) {
            pt ab = b - a, ac = c - a;
            ld sa = ab ^ ac;
            if (sa > 0) return 1;
            if (sa == 0) return 0;
            if (sa < 0) return -1;
        }
    };
};

using mint = Utils::Modular;
using Math = Utils::Numbers;
int n, q, logn, root, ti, last;
vc <vc <int>> g, p;
vc <vc <pii>> to;
vc <int> used, tin, deg, cnt, h;

int precalc (int u, int t = -1) {
    for (int i = 1; i < logn; ++i) {
        p[u][i] = p[p[u][i - 1]][i - 1];
    }
    int ans = inf;
    for (int v: g[u]) {
        if (v != t) {
            h[v] = h[u] + 1;
            int tmp = precalc(v, u);
            ans = min(ans, tmp);
            to[u].pb({tmp, v});
        }
    }
    sort(to[u].begin(), to[u].end());
    ans = min(ans, u);
    return ans;
}

void dfs (int u) {
    tin[u] = ti++;
    for (auto &[mysor, v]: to[u]) {
        dfs(v);
    }
}

bool cmp (int i, int j) {
    return tin[i] < tin[j];
}

void solve () {
    cin >> n >> q;
    ti = 0;
    logn = __lg(n) + 1;
    g.resize(n); p.resize(n, vc <int> (logn)); to.resize(n); used.resize(n); tin.resize(n); deg.resize(n); cnt.resize(n); h.resize(n);
    for (int i = 0; i < n; ++i) {
        int u;
        cin >> u;
        if (u == 0) {
            root = i;
            continue;
        }
        --u;
        g[u].pb(i);
        g[i].pb(u);
        deg[u]++;
        p[i][0] = u;
    }
    forn (i, logn) p[root][i] = root;
    precalc(root);
    auto check = [&](int u) {
        return !used[u];
    };
    dfs(root);
    set <int, decltype(&cmp)> s(cmp);
    forn (i, n) {
        if (deg[i] == 0) {
            s.insert(i);
        }
    }
    while (q--) {
        int cmd, x;
        cin >> cmd >> x;
        if (cmd == 1) {
            while (x--) {
                int u = *s.begin(); last = u;
                int v = p[u][0];
                used[u] = 1;
                if (u != root) {
                    cnt[v]++;
                    if (cnt[v] == deg[v]) {
                        s.insert(v);
                    }
                }
                s.erase(u);
            }
            cout << last + 1 << '\n';
        } else {
            int c = 0; --x;
            if (used[root]) {
                used[root] = 0;
                s.insert(root);
                cout << h[x] << '\n';
                continue;
            }
            for (int l = logn - 1; ~l; --l) {
                if (!check(p[x][l])) {
                    c += (1ll << l);
                    x = p[x][l];
                }
            }
            used[x] = 0;
            if (x != root) {
                --cnt[p[x][0]];
                s.erase(p[x][0]);
            }
            s.insert(x);
            cout << c << '\n';
        }
    }
}
/* Starting and precalcing */
signed main() {
    /* freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); */
    fast;
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In member function 'Utils::Geometric::pt& Utils::Geometric::pt::operator=(Utils::Geometric::pt&)':
ballmachine.cpp:220:66: warning: no return statement in function returning non-void [-Wreturn-type]
  220 |             pt& operator = (pt &b) {this->x = b.x, this->y = b.y;}
      |                                                                  ^
      |                                                                  return *this;
ballmachine.cpp: In function 'void dfs(long long int)':
ballmachine.cpp:282:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  282 |     for (auto &[mysor, v]: to[u]) {
      |                ^

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5