oj.uz

Submission #266330

# Submission time Handle Problem Language Result Execution time Memory
266330 2020-08-15T07:58:42 Z Hehehe Ball Machine (BOI13_ballmachine) C++14
100 / 100
 284 ms 30584 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
//#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 2e5 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int n, dp[N][25], root, mn[N], cnt[N], C, q, viz[N];
vector<int>v[N];

int dfs(int nod){
	int MN = inf;

	for(int it : v[nod]){
		MN = min(dfs(it), MN);
	}

	mn[nod] = min(MN, nod);
	return mn[nod];
}

void dfs2(int nod){
    for(auto it : v[nod]){
        dfs2(it);
    }
    cnt[nod] = C++;
}

void solve(){

    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        cin >> dp[i][0];
        v[dp[i][0]].push_back(i);
        if(dp[i][0] == 0)root = i;
    }

    dfs(root);

    for(int i = 1; i <= n; i++){
        sort(all(v[i]), [](int l, int r){
             return (mn[l] < mn[r]);
        });
    }

    dfs2(root);

    for(int i = 1; i <= 20; i++){
        for(int j = 1; j <= n; j++){
            dp[j][i] = dp[dp[j][i - 1]][i - 1];
        }
    }

    set<pi>s;

    s.insert({inf, 0});
	for(int i = 1; i <= n; i++) s.insert({cnt[i], i});

	while(q--){
        int type, x;
        cin >> type >> x;
        if(type == 1){
            for(int i = 1; i <= x; i++){
                if(i == x)cout << (*s.begin()).ss << '\n';
                viz[(*s.begin()).ss] = 1;
                s.erase(s.begin());
            }
        }else{
            int ans = 0;
            for(int i = 20; i >= 0; i--){
                int p = dp[x][i];
                if(p && viz[p])x = p, ans += (1 << i);
            }
            cout << ans << '\n';
            s.insert({cnt[x], x});
            viz[x] = 0;
        }
	}
}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 141 ms 17656 KB Output is correct
3 Correct 95 ms 17532 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 6 ms 5248 KB Output is correct
7 Correct 6 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 17 ms 5888 KB Output is correct
10 Correct 28 ms 8192 KB Output is correct
11 Correct 164 ms 17660 KB Output is correct
12 Correct 85 ms 17400 KB Output is correct
13 Correct 119 ms 17668 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 10104 KB Output is correct
2 Correct 211 ms 26540 KB Output is correct
3 Correct 133 ms 22900 KB Output is correct
4 Correct 78 ms 12152 KB Output is correct
5 Correct 87 ms 11896 KB Output is correct
6 Correct 73 ms 12024 KB Output is correct
7 Correct 89 ms 11128 KB Output is correct
8 Correct 39 ms 10104 KB Output is correct
9 Correct 198 ms 27000 KB Output is correct
10 Correct 192 ms 26744 KB Output is correct
11 Correct 157 ms 26616 KB Output is correct
12 Correct 190 ms 25080 KB Output is correct
13 Correct 128 ms 27000 KB Output is correct
14 Correct 120 ms 22772 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 16120 KB Output is correct
2 Correct 247 ms 25592 KB Output is correct
3 Correct 163 ms 25080 KB Output is correct
4 Correct 150 ms 22648 KB Output is correct
5 Correct 149 ms 22136 KB Output is correct
6 Correct 162 ms 22136 KB Output is correct
7 Correct 142 ms 21240 KB Output is correct
8 Correct 162 ms 25076 KB Output is correct
9 Correct 241 ms 27128 KB Output is correct
10 Correct 233 ms 26744 KB Output is correct
11 Correct 257 ms 26800 KB Output is correct
12 Correct 242 ms 25592 KB Output is correct
13 Correct 271 ms 30584 KB Output is correct
14 Correct 207 ms 23668 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 27384 KB Output is correct
2 Correct 253 ms 25592 KB Output is correct
3 Correct 189 ms 29688 KB Output is correct
4 Correct 258 ms 27372 KB Output is correct
5 Correct 235 ms 26744 KB Output is correct
6 Correct 188 ms 26744 KB Output is correct
7 Correct 276 ms 25592 KB Output is correct
8 Correct 170 ms 29688 KB Output is correct
9 Correct 116 ms 22900 KB Output is correct