Submission #1037102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037102		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	0 / 100	1095 ms	13660 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
ll n, q, root, deg[mxn], mn[mxn], pr[mxn];
bool state[mxn];
vector<vector<ll>> g(mxn);
void dfs(ll u)
{
    mn[u] = u;
    for (ll i : g[u]) {dfs(i); mn[u] = min(mn[u], mn[i]);}
}
ll push(ll u)
{
    ll opt = -1;
    for (ll i : g[u]) if ((opt == -1 && !state[i]) || (mn[opt] > mn[i] && !state[i])) opt = i;
    if (opt == -1) {state[u] = 1; return u;}
    return push(opt); 
}
ll cnt_push(ll u)
{
    ll opt = -1;
    for (ll i : g[u]) if ((opt == -1 && !state[i]) || (mn[opt] > mn[i] && !state[i])) opt = i;
    if (opt == -1) {state[u] = 1; return 0;}
    return cnt_push(opt)+1; 
}
ll down(ll u)
{
    ll ans = cnt_push(u); // cerr << u << ' ' << ans << '\n'; 
    if (ans) state[u] = 0;
    if (pr[u] && state[pr[u]] && !state[u]) return ans+down(pr[u]);
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> q;
    for (ll i = 1; i <= n; i++)
    {
        ll x; cin >> x; pr[i] = x;
        if (!x) root = i;
        else {g[x].pb(i); deg[x]++;}
    }
    bool ck = 1; dfs(root);
    for (ll i = 1; i <= n; i++) if (deg[i] != 0 && deg[i] != 2) ck = 0;
    if (1)
    {
        while (q--)
        {
            ll type; cin >> type;
            if (type == 1)
            {
                ll k, last = 0; cin >> k;
                while (k--) last = push(root);
                cout << last << '\n';
            }
            else
            {   
                ll x; cin >> x;
                state[x] = 0;
                if (pr[x]) cout << down(pr[x]) << '\n';
                else cout << 0 << '\n';
            }
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:50:10: warning: variable 'ck' set but not used [-Wunused-but-set-variable]
   50 |     bool ck = 1; dfs(root);
      |          ^~

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