Submission #36391

#	Time	Username	Problem	Language	Result	Execution time	Memory
36391		DoanPhuDuc	Ball Machine (BOI13_ballmachine)	C++98	100 / 100	443 ms	21816 KiB

ballmachine

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 1e5 + 10;

int n, q, Root, timer = 0, eulerSize = 0;
int x[N], V[N], c[N], pos[N], euler[N];
int headChain[N], szChain[N], p[N], f[N];

vector <int> adj[N];
set <II> S;

bool CMP(int x, int y) {
    return f[x] < f[y];
}

struct SegmentTree {
    #define m ((l + r) >> 1)
    int st[4 * N];
    void Build(int k, int l, int r) {
        st[k] = 0;
        if (l == r) return;
        Build(k << 1, l, m);
        Build(k << 1 | 1, m + 1, r);
    }
    void Update(int k, int l, int r, int i, int v) {
        if (l == r) {
            st[k] += v;
            return;
        }
        if (i <= m) Update(k << 1, l, m, i, v);
            else Update(k << 1 | 1, m + 1, r, i, v);
        st[k] = st[k << 1] + st[k << 1 | 1];
    }
    int Query(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return 0;
        if (i <= l && r <= j) return st[k];
        return Query(k << 1, l, m, i, j) + Query(k << 1 | 1, m + 1, r, i, j);
    }
    #undef m
} ST;

void EulerTour(int u) {
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k];
        EulerTour(v);
    }
    euler[++eulerSize] = u;
}

void DFS(int u)  {
    c[u] = 1;
    f[u] = u;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k];
        DFS(v);
        c[u] += c[v];
        f[u] = min(f[u], f[v]);
    }
}

void HLD(int u, int par) {
    szChain[par]++;
    headChain[u] = par;
    x[u] = ++timer; V[timer] = u;
    int vtx = 0;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k];
        if (vtx == 0 || c[v] > c[vtx]) vtx = v;
    }
    if (vtx != 0) HLD(vtx, par);
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k]; if (v == vtx) continue;
        HLD(v, v);
    }
}

int Insert(int num) {
    while (num > 0) {
        int u = S.begin() -> second; S.erase(S.begin());
        ST.Update(1, 1, n, x[u], +1);
        num--;
        if (num == 0) return u;
    }
    assert(false);
}

void Add(int i, int v) {
    ST.Update(1, 1, n, i, v);
    S.insert(II(pos[V[i]], V[i]));
}

int Remove(int u, int a = Root) {
    int uChain = headChain[u], aChain = headChain[a];
    int nxt = -1, ans = 0;
    while (true) {
        if (uChain == aChain) {
            int k = ST.Query(1, 1, n, x[a], x[u]);
            int i = x[u] - k + 1;
            if (k == 0) Add(nxt, -1);
                else Add(i, -1);
            ans += k;
            return ans;
        }
        int l = x[uChain], r = x[u];
        int k = ST.Query(1, 1, n, l, r);
        ans += k;
        if (k == 0) {
            Add(nxt, -1);
            return ans;
        } else if (r - l + 1 == k) {
            nxt = x[uChain];
        } else {
            int i = x[u] - k + 1;
            Add(i, -1);
            return ans;
        }
        u = p[uChain]; uChain = headChain[u];
    }
    Add(nxt, -1);
    return ans;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d", &n, &q);
    FOR(i, 1, n) {
        scanf("%d", &p[i]);
        if (p[i] == 0) Root = i;
            else adj[p[i]].push_back(i);
    }
    DFS(Root);
    FOR(i, 1, n) sort(adj[i].begin(), adj[i].end(), CMP);
    HLD(Root, Root);
    EulerTour(Root);
    FOR(i, 1, eulerSize) pos[euler[i]] = i;
    FOR(i, 1, n) S.insert(II(pos[i], i));
    ST.Build(1, 1, n);
    FOR(timer, 1, q) {
        int t, u; scanf("%d%d", &t, &u);
        if (t == 1) printf("%d\n", Insert(u));
            else printf("%d\n", Remove(u) - 1);
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void EulerTour(int)':
ballmachine.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
ballmachine.cpp:55:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
ballmachine.cpp: In function 'void DFS(int)':
ballmachine.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
ballmachine.cpp:65:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
ballmachine.cpp: In function 'void HLD(int, int)':
ballmachine.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
ballmachine.cpp:78:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
ballmachine.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
ballmachine.cpp:83:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:140:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
                          ^
ballmachine.cpp:142:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
                           ^
ballmachine.cpp:154:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t, u; scanf("%d%d", &t, &u);
                                        ^

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