oj.uz

Submission #36391

# Submission time Handle Problem Language Result Execution time Memory
36391 2017-12-08T15:02:25 Z DoanPhuDuc Ball Machine (BOI13_ballmachine) C++
100 / 100
 443 ms 21816 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9468 KB Output is correct
2 Correct 289 ms 13560 KB Output is correct
3 Correct 146 ms 13560 KB Output is correct
4 Correct 0 ms 9468 KB Output is correct
5 Correct 0 ms 9468 KB Output is correct
6 Correct 0 ms 9600 KB Output is correct
7 Correct 3 ms 9600 KB Output is correct
8 Correct 3 ms 9600 KB Output is correct
9 Correct 9 ms 9732 KB Output is correct
10 Correct 56 ms 10524 KB Output is correct
11 Correct 269 ms 13560 KB Output is correct
12 Correct 123 ms 13560 KB Output is correct
13 Correct 223 ms 13560 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11648 KB Output is correct
2 Correct 303 ms 18284 KB Output is correct
3 Correct 116 ms 15564 KB Output is correct
4 Correct 123 ms 12156 KB Output is correct
5 Correct 126 ms 12020 KB Output is correct
6 Correct 106 ms 12020 KB Output is correct
7 Correct 129 ms 11516 KB Output is correct
8 Correct 46 ms 11652 KB Output is correct
9 Correct 286 ms 18816 KB Output is correct
10 Correct 306 ms 18288 KB Output is correct
11 Correct 199 ms 18288 KB Output is correct
12 Correct 313 ms 16956 KB Output is correct
13 Correct 173 ms 20344 KB Output is correct
14 Correct 123 ms 15564 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 14080 KB Output is correct
2 Correct 376 ms 17112 KB Output is correct
3 Correct 193 ms 19292 KB Output is correct
4 Correct 209 ms 16892 KB Output is correct
5 Correct 216 ms 16500 KB Output is correct
6 Correct 256 ms 16496 KB Output is correct
7 Correct 253 ms 15556 KB Output is correct
8 Correct 186 ms 19296 KB Output is correct
9 Correct 403 ms 18812 KB Output is correct
10 Correct 396 ms 18288 KB Output is correct
11 Correct 413 ms 18288 KB Output is correct
12 Correct 399 ms 17112 KB Output is correct
13 Correct 333 ms 21816 KB Output is correct
14 Correct 359 ms 15552 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 18820 KB Output is correct
2 Correct 429 ms 17116 KB Output is correct
3 Correct 186 ms 21816 KB Output is correct
4 Correct 346 ms 18816 KB Output is correct
5 Correct 316 ms 18288 KB Output is correct
6 Correct 266 ms 18288 KB Output is correct
7 Correct 443 ms 17112 KB Output is correct
8 Correct 196 ms 21816 KB Output is correct
9 Correct 143 ms 15556 KB Output is correct