oj.uz

Submission #667238

# Submission time Handle Problem Language Result Execution time Memory
667238 2022-11-30T21:33:17 Z AmirH Ball Machine (BOI13_ballmachine) C++14
100 / 100
 562 ms 49096 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 8 ms 14804 KB Output is correct
2 Correct 138 ms 29840 KB Output is correct
3 Correct 77 ms 30096 KB Output is correct
4 Correct 7 ms 14804 KB Output is correct
5 Correct 7 ms 14804 KB Output is correct
6 Correct 8 ms 15060 KB Output is correct
7 Correct 8 ms 15060 KB Output is correct
8 Correct 9 ms 15088 KB Output is correct
9 Correct 14 ms 15796 KB Output is correct
10 Correct 31 ms 18516 KB Output is correct
11 Correct 147 ms 29904 KB Output is correct
12 Correct 76 ms 30060 KB Output is correct
13 Correct 120 ms 29972 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 21216 KB Output is correct
2 Correct 500 ms 43184 KB Output is correct
3 Correct 104 ms 37860 KB Output is correct
4 Correct 119 ms 23392 KB Output is correct
5 Correct 201 ms 23400 KB Output is correct
6 Correct 186 ms 23376 KB Output is correct
7 Correct 168 ms 22004 KB Output is correct
8 Correct 54 ms 21192 KB Output is correct
9 Correct 307 ms 43252 KB Output is correct
10 Correct 479 ms 43100 KB Output is correct
11 Correct 389 ms 43332 KB Output is correct
12 Correct 362 ms 39964 KB Output is correct
13 Correct 179 ms 44888 KB Output is correct
14 Correct 109 ms 37828 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 29124 KB Output is correct
2 Correct 562 ms 40696 KB Output is correct
3 Correct 313 ms 42052 KB Output is correct
4 Correct 205 ms 37692 KB Output is correct
5 Correct 298 ms 37572 KB Output is correct
6 Correct 300 ms 37600 KB Output is correct
7 Correct 254 ms 35388 KB Output is correct
8 Correct 304 ms 42080 KB Output is correct
9 Correct 324 ms 43480 KB Output is correct
10 Correct 545 ms 43528 KB Output is correct
11 Correct 544 ms 43464 KB Output is correct
12 Correct 555 ms 40664 KB Output is correct
13 Correct 553 ms 49096 KB Output is correct
14 Correct 150 ms 37900 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 43536 KB Output is correct
2 Correct 509 ms 40656 KB Output is correct
3 Correct 188 ms 48788 KB Output is correct
4 Correct 381 ms 43552 KB Output is correct
5 Correct 529 ms 43460 KB Output is correct
6 Correct 385 ms 43424 KB Output is correct
7 Correct 490 ms 40644 KB Output is correct
8 Correct 191 ms 48828 KB Output is correct
9 Correct 102 ms 37908 KB Output is correct