oj.uz

Submission #36387

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

bool ban[N];

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

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

int Insert(int num) {
    while (num > 0) {
        int u = S.begin() -> second; S.erase(S.begin());
        ban[u] = true;
        --num;
        if (num == 0) return u;
    }
    assert(false);
}


int Remove(int u) {
    int ans = 0;
    while (ban[p[u]] == true) {
        ++ans;
        u = p[u];
    }
    ban[u] = false;
    S.insert(II(pos[u], u));
    return ans;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("ans.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());
    EulerTour(Root);
    FOR(i, 1, eulerSize) pos[euler[i]] = i;
    FOR(i, 1, n) S.insert(II(pos[i], i));
    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));
    }

    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:27:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:61: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:63:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
                           ^
ballmachine.cpp:72: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 Incorrect 0 ms 7588 KB Output isn't correct
2 Execution timed out 1000 ms 11680 KB Execution timed out
3 Incorrect 113 ms 11680 KB Output isn't correct
4 Execution timed out 1000 ms 7588 KB Execution timed out
5 Incorrect 0 ms 7588 KB Output isn't correct
6 Incorrect 0 ms 7720 KB Output isn't correct
7 Execution timed out 1000 ms 7720 KB Execution timed out
8 Execution timed out 1000 ms 7720 KB Execution timed out
9 Incorrect 9 ms 7852 KB Output isn't correct
10 Execution timed out 1000 ms 8644 KB Execution timed out
11 Incorrect 216 ms 11680 KB Output isn't correct
12 Incorrect 106 ms 11680 KB Output isn't correct
13 Incorrect 143 ms 11680 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9488 KB Output is correct
2 Execution timed out 1000 ms 15620 KB Execution timed out
3 Incorrect 143 ms 13684 KB Output isn't correct
4 Execution timed out 1000 ms 10048 KB Execution timed out
5 Execution timed out 1000 ms 9912 KB Execution timed out
6 Incorrect 203 ms 9908 KB Output isn't correct
7 Incorrect 123 ms 9528 KB Output isn't correct
8 Correct 59 ms 9488 KB Output is correct
9 Incorrect 246 ms 16152 KB Output isn't correct
10 Execution timed out 1000 ms 15624 KB Execution timed out
11 Incorrect 226 ms 15620 KB Output isn't correct
12 Incorrect 706 ms 14692 KB Output isn't correct
13 Correct 159 ms 17084 KB Output is correct
14 Incorrect 119 ms 13684 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 11812 KB Execution timed out
2 Execution timed out 1000 ms 14848 KB Execution timed out
3 Execution timed out 1000 ms 16168 KB Execution timed out
4 Execution timed out 1000 ms 14392 KB Execution timed out
5 Execution timed out 1000 ms 13992 KB Execution timed out
6 Execution timed out 1000 ms 13988 KB Execution timed out
7 Execution timed out 1000 ms 13372 KB Execution timed out
8 Execution timed out 1000 ms 16164 KB Execution timed out
9 Execution timed out 1000 ms 16156 KB Execution timed out
10 Execution timed out 1000 ms 15628 KB Execution timed out
11 Execution timed out 1000 ms 15628 KB Execution timed out
12 Execution timed out 1000 ms 14844 KB Execution timed out
13 Execution timed out 1000 ms 18380 KB Execution timed out
14 Incorrect 199 ms 13672 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 16156 KB Execution timed out
2 Execution timed out 1000 ms 14844 KB Execution timed out
3 Correct 179 ms 18376 KB Output is correct
4 Execution timed out 1000 ms 16152 KB Execution timed out
5 Execution timed out 1000 ms 15620 KB Execution timed out
6 Incorrect 306 ms 15620 KB Output isn't correct
7 Execution timed out 1000 ms 14844 KB Execution timed out
8 Correct 186 ms 18376 KB Output is correct
9 Incorrect 103 ms 13676 KB Output isn't correct