oj.uz

Submission #36386

# Submission time Handle Problem Language Result Execution time Memory
36386 2017-12-08T14:41:49 Z DoanPhuDuc Ball Machine (BOI13_ballmachine) C++
16.1111 / 100
 1000 ms 21432 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];

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

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;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k];
        DFS(v);
        c[u] += c[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);
    }
    FOR(i, 1, n) sort(adj[i].begin(), adj[i].end());
    DFS(Root);
    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:51: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:60: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:72: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:77:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:134: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:136:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
                           ^
ballmachine.cpp:148: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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 9080 KB Execution timed out
2 Execution timed out 1000 ms 13172 KB Execution timed out
3 Incorrect 136 ms 13172 KB Output isn't correct
4 Execution timed out 1000 ms 9080 KB Execution timed out
5 Execution timed out 1000 ms 9080 KB Execution timed out
6 Incorrect 0 ms 9212 KB Output isn't correct
7 Incorrect 0 ms 9212 KB Output isn't correct
8 Execution timed out 1000 ms 9212 KB Execution timed out
9 Execution timed out 1000 ms 9344 KB Execution timed out
10 Execution timed out 1000 ms 10136 KB Execution timed out
11 Incorrect 323 ms 13172 KB Output isn't correct
12 Incorrect 133 ms 13172 KB Output isn't correct
13 Incorrect 176 ms 13172 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11260 KB Output is correct
2 Execution timed out 1000 ms 17892 KB Execution timed out
3 Incorrect 146 ms 15176 KB Output isn't correct
4 Execution timed out 1000 ms 11768 KB Execution timed out
5 Execution timed out 1000 ms 11636 KB Execution timed out
6 Incorrect 126 ms 11640 KB Output isn't correct
7 Execution timed out 1000 ms 11124 KB Execution timed out
8 Correct 46 ms 11264 KB Output is correct
9 Incorrect 273 ms 18428 KB Output isn't correct
10 Execution timed out 1000 ms 17900 KB Execution timed out
11 Incorrect 249 ms 17900 KB Output isn't correct
12 Incorrect 286 ms 16568 KB Output isn't correct
13 Correct 216 ms 19960 KB Output is correct
14 Incorrect 133 ms 15176 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 13692 KB Output isn't correct
2 Incorrect 336 ms 16724 KB Output isn't correct
3 Correct 183 ms 18912 KB Output is correct
4 Incorrect 206 ms 16504 KB Output isn't correct
5 Incorrect 243 ms 16112 KB Output isn't correct
6 Incorrect 233 ms 16112 KB Output isn't correct
7 Incorrect 249 ms 15176 KB Output isn't correct
8 Correct 186 ms 18912 KB Output is correct
9 Incorrect 336 ms 18432 KB Output isn't correct
10 Incorrect 383 ms 17900 KB Output isn't correct
11 Incorrect 353 ms 17900 KB Output isn't correct
12 Incorrect 376 ms 16732 KB Output isn't correct
13 Correct 369 ms 21432 KB Output is correct
14 Incorrect 259 ms 15164 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 18432 KB Execution timed out
2 Incorrect 313 ms 16724 KB Output isn't correct
3 Correct 173 ms 21432 KB Output is correct
4 Execution timed out 1000 ms 18424 KB Execution timed out
5 Incorrect 333 ms 17896 KB Output isn't correct
6 Incorrect 246 ms 17900 KB Output isn't correct
7 Incorrect 329 ms 16724 KB Output isn't correct
8 Correct 243 ms 21428 KB Output is correct
9 Incorrect 129 ms 15168 KB Output isn't correct