oj.uz

Submission #386183

# Submission time Handle Problem Language Result Execution time Memory
386183 2021-04-06T03:54:39 Z ak2006 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 353 ms 34796 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 1e5 + 5,root = -1,q;
int timer = 0;
vvi adj(n),dp(n,vi(21));
vi out(n),minNode(n),dep(n);
vb is(n);
set<pair<int,int>>unfilled;
bool cmp(int u,int v)
{
    return minNode[u] < minNode[v];
}
int compute(int u,int p)
{
    minNode[u] = u;
    for (int v:adj[u])if (v != p)minNode[u] = min(minNode[u],compute(v,u));
    return minNode[u];
}
void dfs(int u,int p)
{
    dep[u] = dep[p] + 1;
    dp[u][0] = p;
    for (int i = 1;i<=20;i++)dp[u][i] = dp[dp[u][i - 1]][i - 1];
    sort(adj[u].begin(),adj[u].end(),cmp);
    for (int v:adj[u]){
        if (v == p)continue;
        dfs(v,u);
    }
    out[u] = ++timer;
    unfilled.insert({out[u],u});
}
int add()
{
    auto it = unfilled.begin();
    unfilled.erase(it);
    is[(*it).second] = 1;
    return (*it).second;
}
int sub(int u)
{
    int v = u;
    for (int i = 20;i>=0;i--){
        if (is[dp[v][i]])v = dp[v][i];
    }
    is[v] = 0;
    unfilled.insert({out[v],v});
    return dep[u] - dep[v];
}
int main()
{
    fast;
    cin>>n>>q;
    for (int i = 0;i<n;i++){
        int p;
        cin>>p;
        p--;
        if (p == -1)root = i;
        else adj[p].pb(i);
    }
    compute(root,root);
    dfs(root,root);
    while (q--){
        int t,u;
        cin>>t>>u;
        if (t == 1){
            while (u-- > 1)add();
            cout<<add() + 1<<'\n';
        }
        else{
            cout<<sub(u - 1)<<'\n';
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15596 KB Output is correct
2 Correct 198 ms 21100 KB Output is correct
3 Correct 109 ms 21100 KB Output is correct
4 Correct 15 ms 15596 KB Output is correct
5 Correct 15 ms 15596 KB Output is correct
6 Correct 19 ms 15724 KB Output is correct
7 Correct 16 ms 15744 KB Output is correct
8 Correct 17 ms 15724 KB Output is correct
9 Correct 23 ms 15980 KB Output is correct
10 Correct 40 ms 16876 KB Output is correct
11 Correct 194 ms 21040 KB Output is correct
12 Correct 110 ms 21100 KB Output is correct
13 Correct 151 ms 21100 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 19672 KB Output is correct
2 Correct 293 ms 28544 KB Output is correct
3 Correct 133 ms 22888 KB Output is correct
4 Correct 108 ms 20076 KB Output is correct
5 Correct 110 ms 19948 KB Output is correct
6 Correct 103 ms 19948 KB Output is correct
7 Correct 112 ms 19052 KB Output is correct
8 Correct 62 ms 19564 KB Output is correct
9 Correct 248 ms 28908 KB Output is correct
10 Correct 294 ms 28524 KB Output is correct
11 Correct 254 ms 28524 KB Output is correct
12 Correct 272 ms 25964 KB Output is correct
13 Correct 215 ms 32364 KB Output is correct
14 Correct 130 ms 22888 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 22340 KB Output is correct
2 Correct 332 ms 26348 KB Output is correct
3 Correct 232 ms 30700 KB Output is correct
4 Correct 211 ms 26220 KB Output is correct
5 Correct 214 ms 25836 KB Output is correct
6 Correct 232 ms 26020 KB Output is correct
7 Correct 207 ms 23916 KB Output is correct
8 Correct 229 ms 30700 KB Output is correct
9 Correct 303 ms 29164 KB Output is correct
10 Correct 336 ms 28708 KB Output is correct
11 Correct 338 ms 28652 KB Output is correct
12 Correct 339 ms 26348 KB Output is correct
13 Correct 353 ms 34796 KB Output is correct
14 Correct 228 ms 23272 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 29292 KB Output is correct
2 Correct 316 ms 26428 KB Output is correct
3 Correct 241 ms 34412 KB Output is correct
4 Correct 287 ms 29164 KB Output is correct
5 Correct 318 ms 28652 KB Output is correct
6 Correct 268 ms 28652 KB Output is correct
7 Correct 316 ms 26348 KB Output is correct
8 Correct 254 ms 34412 KB Output is correct
9 Correct 129 ms 22888 KB Output is correct