Submission #126051

#	Time	Username	Problem	Language	Result	Execution time	Memory
126051		wasyl	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	219 ms	29816 KiB

ballmachine

#include <bits/stdc++.h>
#ifndef DBG
#define dbg(...)
#else
#define dbg(...) {cerr << "\033[1;96m"; __VA_ARGS__; cerr << "\033[0m";} 
#endif
#define bgn(...) begin(__VA_ARGS__)
#define rsz(...) resize(__VA_ARGS__)
#define emp(...) emplace_back(__VA_ARGS__)
#define psh(...) push_back(__VA_ARGS__)
#define ddmp(...) dbg(dmp(__VA_ARGS__))
#define prt(...) print(cout, __VA_ARGS__)
#define dprt(...) dbg(print(cerr, __VA_ARGS__))
#define dmp(...) print(cerr, #__VA_ARGS__, '=', __VA_ARGS__)
#define all(...) bgn(__VA_ARGS__), end(__VA_ARGS__)
#define siz(...) static_cast< int >((__VA_ARGS__).size())
using namespace std; using ll = long long;
template< typename... t > using V = vector< t... >;
template< typename... t > using outit = ostream_iterator< t... >;
template< typename t > void print(ostream& os, const t& a)
{os << a <<  '\n';} template< typename t, typename... v >
void print(ostream& os, const t& a, v&&... b){os << a << ' '; print(os, b...);}

constexpr int maxn = 1e5, logg = 20;

int n, q, t;
bool occ[maxn + 1];
int mi[maxn + 1];
int cnt[maxn + 1];
int sk[maxn + 1][logg];
int tb[maxn + 1], bt[maxn + 1];
set< pair< int, int > > S;
V< int > gr[maxn + 1];

void dfs1(int v, int oj)
{
    ddmp(v, oj);
    mi[v] = v;
    for (int s : gr[v])
        if (s != oj)
            dfs1(s, v), mi[v] = min(mi[v], mi[s]);
}

void dfs2(int v, int oj)
{
    dprt("dfs2");
    ddmp(v, oj);
    sk[v][0] = oj;
    tb[v] = ++t;
    bt[t] = v;

    V< pair< int, int > > ilo;
    for (int s : gr[v])
        if (s != oj)
            ilo.psh({mi[s], s});

    sort(all(ilo));

    for (auto& p : ilo)
        dfs2(p.second, v);
}

inline int zrzuc()
{
    dprt("zrzuc");
    assert(not S.empty());
    int v = (*S.begin()).second;
    S.erase(S.begin());
    occ[v] = true;
    ++cnt[sk[v][0]];
    if (sk[v][0] != 0 and cnt[sk[v][0]] == gr[sk[v][0]].size())
        S.insert({tb[sk[v][0]], sk[v][0]});

    return v;
}

inline int usun(int v)
{
    dprt("usun");
    dprt(v);
    int sum = 0;
    for (int i = logg - 1; i >= 0; --i)
        if (occ[sk[v][i]])
        {
            sum += (1 << i);
            v = sk[v][i];
        }
    ddmp(v);

    occ[v] = false;
    
    if (sk[v][0] != 0 and cnt[sk[v][0]] == gr[sk[v][0]].size())
    {
        assert(occ[sk[v][0]] == false);
        assert(S.find({tb[sk[v][0]], sk[v][0]}) != S.end());
        S.erase(S.find({tb[sk[v][0]], sk[v][0]}));
    }

    --cnt[sk[v][0]];

    S.insert({tb[v], v});

    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        int v; cin >> v;
        gr[v].psh(i);
    }

    dfs1(0, 0);
    dfs2(0, 0);
    
    for (int i = 1; i < logg; ++i)
        for (int k = 1; k <= n; ++k)
            sk[k][i] = sk[sk[k][i - 1]][i - 1];

    for (int i = 1; i <= n; ++i)
        if (gr[i].size() == cnt[i])
            S.insert({tb[i], i});

    for (int i = 0; i < q; ++i)
    {
        int t, v; cin >> t >> v;
        if (t == 1)
            while (v--)
            {
                if (v == 0)
                    prt(zrzuc());
                else
                    zrzuc();
            }
        if (t == 2)
            prt(usun(v));
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int zrzuc()':
ballmachine.cpp:71:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (sk[v][0] != 0 and cnt[sk[v][0]] == gr[sk[v][0]].size())
                           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int usun(int)':
ballmachine.cpp:92:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (sk[v][0] != 0 and cnt[sk[v][0]] == gr[sk[v][0]].size())
                           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:127:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (gr[i].size() == cnt[i])
             ~~~~~~~~~~~~~^~~~~~~~~

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