oj.uz

Submission #447651

# Submission time Handle Problem Language Result Execution time Memory
447651 2021-07-27T08:25:16 Z prvocislo Ball Machine (BOI13_ballmachine) C++17
46.7643 / 100
 1000 ms 27964 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5, logn = 17;
int l[logn][maxn], mini[maxn], inv[maxn], n, q;
vector<pair<int, int> > g[maxn];
vector<int> ord;
void dfs1(int u, int p = -1)
{
    for (int i = 1; i < logn; i++) if (l[i-1][u] != -1) l[i][u] = l[i-1][l[i-1][u]];
    for (pair<int, int> &v : g[u]) if (v.first != p) 
    {
        l[0][v.first] = u;
        dfs1(v.first, u);
        v.second = mini[v.first];
        mini[u] = min(mini[u], mini[v.first]);
    }
}
void dfs2(int u, int p = -1)
{
    for (pair<int, int> &v : g[u]) if (v.first != p) 
        dfs2(v.first, u);
    inv[ord.size()] = u, ord.push_back(u);
}
bool cmp(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    iota(mini, mini+n, 0);
    int root = -1;
    for (int i = 0, p; i < n; i++)
    {
        cin >> p; p--;
        if (p == -1) root = i;
        else g[p].push_back({i, -1});
    }
    for (int i = 0; i < logn; i++) for (int j = 0; j < n; j++) l[i][j] = -1;
    dfs1(root); 
    for (int i = 0; i < n; i++) sort(g[i].begin(), g[i].end(), cmp);
    dfs2(root);
    set<int> s;
    for (int i = 0; i < n; i++) s.insert(i);
    vector<bool> b(n, false);
    while (q--)
    {
        int typ; cin >> typ;
        if (typ == 1)
        {
           int k; cin >> k;
           int ans = -1;
           for (int i = 0; i < k; i++)
           {
                int vr = ord[*s.begin()];
                ans = vr;
                b[vr] = true;
                s.erase(s.begin());
           }
           cout << ans+1 << "\n";
        }
        else
        {
            int x; cin >> x; x--;
            int y = x, ans = 0;
            for (int i = logn-1; i >= 0; i--) if (l[i][y] != -1 && b[l[i][y]]) y = l[i][y], ans += (1 << i);
            b[y] = false; s.insert(inv[y]);
            cout << ans << "\n";
        }
    }
    return 0;
}

Subtask #1
1.92307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2764 KB Output isn't correct
2 Execution timed out 1088 ms 13240 KB Time limit exceeded
3 Incorrect 80 ms 13244 KB Output isn't correct
4 Execution timed out 1082 ms 2636 KB Time limit exceeded
5 Incorrect 2 ms 2764 KB Output isn't correct
6 Correct 3 ms 2892 KB Output is correct
7 Execution timed out 1091 ms 2808 KB Time limit exceeded
8 Execution timed out 1090 ms 2892 KB Time limit exceeded
9 Execution timed out 1089 ms 3404 KB Time limit exceeded
10 Execution timed out 1093 ms 5308 KB Time limit exceeded
11 Execution timed out 1089 ms 12940 KB Time limit exceeded
12 Incorrect 81 ms 13248 KB Output isn't correct
13 Incorrect 120 ms 13408 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 7772 KB Output isn't correct
2 Incorrect 213 ms 23028 KB Output isn't correct
3 Correct 104 ms 17852 KB Output is correct
4 Execution timed out 1082 ms 9132 KB Time limit exceeded
5 Execution timed out 1088 ms 8644 KB Time limit exceeded
6 Execution timed out 1093 ms 9200 KB Time limit exceeded
7 Execution timed out 1095 ms 8132 KB Time limit exceeded
8 Incorrect 39 ms 7744 KB Output isn't correct
9 Incorrect 207 ms 23208 KB Output isn't correct
10 Incorrect 211 ms 22876 KB Output isn't correct
11 Incorrect 190 ms 22772 KB Output isn't correct
12 Incorrect 208 ms 20444 KB Output isn't correct
13 Incorrect 121 ms 24896 KB Output isn't correct
14 Correct 108 ms 17828 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 13048 KB Output is correct
2 Correct 222 ms 20932 KB Output is correct
3 Correct 150 ms 22720 KB Output is correct
4 Correct 137 ms 19056 KB Output is correct
5 Correct 143 ms 18672 KB Output is correct
6 Correct 139 ms 18640 KB Output is correct
7 Correct 131 ms 17084 KB Output is correct
8 Correct 152 ms 22688 KB Output is correct
9 Correct 213 ms 23236 KB Output is correct
10 Correct 221 ms 22852 KB Output is correct
11 Correct 232 ms 22844 KB Output is correct
12 Correct 242 ms 20884 KB Output is correct
13 Correct 271 ms 27964 KB Output is correct
14 Correct 176 ms 18312 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 23380 KB Time limit exceeded
2 Incorrect 214 ms 20908 KB Output isn't correct
3 Incorrect 136 ms 27656 KB Output isn't correct
4 Execution timed out 1086 ms 23320 KB Time limit exceeded
5 Incorrect 211 ms 22848 KB Output isn't correct
6 Incorrect 185 ms 22772 KB Output isn't correct
7 Incorrect 218 ms 20988 KB Output isn't correct
8 Incorrect 140 ms 27620 KB Output isn't correct
9 Correct 104 ms 17876 KB Output is correct