oj.uz

Submission #667236

# Submission time Handle Problem Language Result Execution time Memory
667236 2022-11-30T21:30:45 Z AmirH Ball Machine (BOI13_ballmachine) C++14
100 / 100
 637 ms 49140 KB 
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<bitset>
#include<queue>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<unordered_map>
#include<list>
#include<utility>
#include<stack>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
#define cl clear
#define F  first
#define S  second
#define pb push_back
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int MAX_N = 2e5 + 25;
const ll INF = 1e18;
const int inf = 1e9;
void free() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}
vector<int> vtx[MAX_N];
set<pii> adj[MAX_N];
int mini[MAX_N];
vector<int> res;
int par[MAX_N];
set<int> notseen;
int ar[MAX_N];
int pr[MAX_N];
int height[MAX_N];
int lcm[MAX_N][20];
int listpo[MAX_N];

int get_height(int v, int h) {
    if(h == 0)
        return v;
    int max_z = listpo[h];
    return get_height(lcm[v][max_z], h - (1 << max_z));
}

int get_last_seen(int v) {
    int l = 0, r = height[v] + 1;
    while(r - l > 1) {
        int mid = (l + r) / 2;
        if(notseen.find(ar[get_height(v, mid)]) == notseen.end())
            l = mid;
        else
            r = mid;
    }
    return get_height(v, l);
}

void find_po() {
    int j = 0;
    for(int i  = 1; i <= 1e5; i++) {
        if(i >= (1 << (j + 1))) {
            j++;
            listpo[i] = j;
        }
        else
            listpo[i] = j;
    }
}

void rmq(int v) {
    queue<int> q;
    q.push(v);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(auto i : vtx[x]) {
            if(height[i] > height[x])
                q.push(i);
        }
        for(int i = 0; (1 << i) <= height[x]; i++) {
            if(i == 0)
                lcm[x][i] = par[x];
            else
                lcm[x][i] = lcm[lcm[x][i - 1]][i - 1];
        }
    }
}

void dfs2(int v) {
    for(auto i : adj[v])
        dfs2(i.second);
    res.pb(v);
}
void dfs(int v, int s) {
    mini[v] = v;
    for(auto i : vtx[v]) {
        if(i != s) {
            height[i] = height[v] + 1;
            dfs(i, v);
            mini[v] = min(mini[v], mini[i]);
            adj[v].insert({mini[i], i});
        }
    }
}
int main() {
    faster; //free();
    find_po();
    int n, q; cin >> n >> q;
    int st;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        par[i] = x;
        if(x == 0) {
            st = i;
        }
        else {
            vtx[x].pb(i);
            vtx[i].pb(x);
        }
    }
    height[st] = 0;
    dfs(st, 0);
    dfs2(st);
    rmq(st);
    for(int i = 0; i < res.size(); i++) {
        ar[res[i]] = i + 1;
        pr[i + 1] = res[i];
    }
    for(int i = 1; i <= n; i++)
        notseen.insert(i);
    while(q--) {
        int t, x; cin >> t >> x;
        if(t == 1) {
            int ft;
            while(x--) {
                ft = pr[*notseen.begin()];
                notseen.erase(notseen.begin());
            }
            cout << ft << '\n';
        }
        if(t == 2) {
            int sec = get_last_seen(x);
            notseen.insert(ar[sec]);
            cout << height[x] - height[sec] << '\n';
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for(int i = 0; i < res.size(); i++) {
      |                    ~~^~~~~~~~~~~~
ballmachine.cpp: In function 'void free()':
ballmachine.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:148:27: warning: 'ft' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |             cout << ft << '\n';
      |                           ^~~~
ballmachine.cpp:133:8: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |     rmq(st);
      |     ~~~^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14804 KB Output is correct
2 Correct 137 ms 29900 KB Output is correct
3 Correct 79 ms 30040 KB Output is correct
4 Correct 8 ms 14852 KB Output is correct
5 Correct 8 ms 14804 KB Output is correct
6 Correct 8 ms 15060 KB Output is correct
7 Correct 8 ms 14980 KB Output is correct
8 Correct 9 ms 14992 KB Output is correct
9 Correct 14 ms 15700 KB Output is correct
10 Correct 32 ms 18608 KB Output is correct
11 Correct 153 ms 29836 KB Output is correct
12 Correct 96 ms 30120 KB Output is correct
13 Correct 120 ms 29896 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 21316 KB Output is correct
2 Correct 519 ms 43204 KB Output is correct
3 Correct 111 ms 37828 KB Output is correct
4 Correct 154 ms 23456 KB Output is correct
5 Correct 202 ms 23432 KB Output is correct
6 Correct 202 ms 23484 KB Output is correct
7 Correct 172 ms 21964 KB Output is correct
8 Correct 57 ms 21232 KB Output is correct
9 Correct 369 ms 43504 KB Output is correct
10 Correct 518 ms 43200 KB Output is correct
11 Correct 384 ms 43132 KB Output is correct
12 Correct 414 ms 39800 KB Output is correct
13 Correct 171 ms 44992 KB Output is correct
14 Correct 105 ms 37796 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 29064 KB Output is correct
2 Correct 566 ms 40600 KB Output is correct
3 Correct 352 ms 42060 KB Output is correct
4 Correct 237 ms 37668 KB Output is correct
5 Correct 323 ms 37744 KB Output is correct
6 Correct 323 ms 37612 KB Output is correct
7 Correct 291 ms 35424 KB Output is correct
8 Correct 305 ms 42076 KB Output is correct
9 Correct 336 ms 43460 KB Output is correct
10 Correct 582 ms 43308 KB Output is correct
11 Correct 562 ms 43452 KB Output is correct
12 Correct 556 ms 40708 KB Output is correct
13 Correct 571 ms 49140 KB Output is correct
14 Correct 141 ms 37952 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 43524 KB Output is correct
2 Correct 503 ms 40652 KB Output is correct
3 Correct 188 ms 48876 KB Output is correct
4 Correct 390 ms 43444 KB Output is correct
5 Correct 637 ms 43348 KB Output is correct
6 Correct 415 ms 43292 KB Output is correct
7 Correct 550 ms 40580 KB Output is correct
8 Correct 216 ms 48844 KB Output is correct
9 Correct 111 ms 37940 KB Output is correct