oj.uz

Submission #520892

# Submission time Handle Problem Language Result Execution time Memory
520892 2022-01-31T11:53:39 Z SmolBrain Ball Machine (BOI13_ballmachine) C++17
100 / 100
 509 ms 28340 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define conts continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define ff first
#define ss second
#define ceil2(x,y) ((x+y-1) / (y))
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; print(x); cout << endl
#else
#define debug(x)
#endif

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define trav(i,a) for(auto &i : a)

bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}

void print(ll t) {cout << t;}
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
void print(ld t) {cout << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = ll(1e18) + 5;

int curr = 1;
const int LOG = 17;
vector<vector<int>> up(maxn, vector<int>(LOG));
vector<int> adj[maxn], submn(maxn), order(maxn), depth(maxn);

void dfs1(int node, int par) {
    submn[node] = node;
    trav(child, adj[node]) {
        if (child == par) conts;

        up[child][0] = node;
        rep1(j, LOG - 1){
            up[child][j] = up[ up[child][j-1] ][j-1];
        }

        depth[child] = depth[node] + 1;

        dfs1(child, node);
        submn[node] = min(submn[node], submn[child]);
    }
}

void dfs2(int node, int par) {
    trav(child, adj[node]) {
        if (child == par) conts;
        dfs2(child, node);
    }

    order[node] = curr++;
}

void solve(int test_case)
{
    int n, q; cin >> n >> q;
    int root;

    rep1(i, n) {
        int u; cin >> u;
        if (u == 0) root = i;
        else {
            adj[i].pb(u), adj[u].pb(i);
        }
    }

    rep(j, LOG){
        up[root][j] = root;
    }

    dfs1(root, -1);

    auto comp = [&](int x, int y) {
        if (submn[x] < submn[y]) return true;
        else return false;
    };

    rep1(i, n) {
        sort(all(adj[i]), comp);
    }

    dfs2(root, -1);

    // set s stores all free nodes in the order they appear
    set<pair<int,int>> s;
    rep1(i,n){
        s.insert({order[i], i});
    }

    while(q--){
        int t; cin >> t;
        if(t == 1){
            int k; cin >> k;
            int last;

            while(k--){
                auto p = *s.begin();
                s.erase(s.begin());
                last = p.ss;
            }

            cout << last << endl;
        }
        else{
            int u; cin >> u;
            int ou = u;

            for(int j = LOG - 1; j >= 0; --j){
                int ances = up[u][j];
                pair<int,int> key = {order[ances], ances};
                if(s.count(key)) conts;

                u = up[u][j];
            }

            int ans = depth[ou] - depth[u];
            cout << ans << endl;
            s.insert({order[u], u});
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;
    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'void usaco(std::string)':
ballmachine.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void solve(int)':
ballmachine.cpp:13:14: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 | #define endl '\n'
      |              ^~~~
ballmachine.cpp:136:17: note: 'last' was declared here
  136 |             int last;
      |                 ^~~~
ballmachine.cpp:110:16: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |         up[root][j] = root;
      |                ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14028 KB Output is correct
2 Correct 192 ms 20556 KB Output is correct
3 Correct 111 ms 20444 KB Output is correct
4 Correct 11 ms 14028 KB Output is correct
5 Correct 11 ms 14028 KB Output is correct
6 Correct 11 ms 14092 KB Output is correct
7 Correct 12 ms 14028 KB Output is correct
8 Correct 11 ms 14040 KB Output is correct
9 Correct 18 ms 14408 KB Output is correct
10 Correct 39 ms 15540 KB Output is correct
11 Correct 202 ms 20528 KB Output is correct
12 Correct 119 ms 20396 KB Output is correct
13 Correct 166 ms 20400 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 17092 KB Output is correct
2 Correct 451 ms 25736 KB Output is correct
3 Correct 155 ms 23188 KB Output is correct
4 Correct 143 ms 17880 KB Output is correct
5 Correct 203 ms 17944 KB Output is correct
6 Correct 194 ms 17956 KB Output is correct
7 Correct 174 ms 17528 KB Output is correct
8 Correct 54 ms 16980 KB Output is correct
9 Correct 327 ms 25752 KB Output is correct
10 Correct 406 ms 25732 KB Output is correct
11 Correct 361 ms 25792 KB Output is correct
12 Correct 381 ms 24340 KB Output is correct
13 Correct 157 ms 26448 KB Output is correct
14 Correct 142 ms 23136 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 19948 KB Output is correct
2 Correct 472 ms 24772 KB Output is correct
3 Correct 260 ms 25212 KB Output is correct
4 Correct 229 ms 23348 KB Output is correct
5 Correct 369 ms 23308 KB Output is correct
6 Correct 313 ms 23260 KB Output is correct
7 Correct 246 ms 22340 KB Output is correct
8 Correct 248 ms 25224 KB Output is correct
9 Correct 377 ms 25880 KB Output is correct
10 Correct 431 ms 25884 KB Output is correct
11 Correct 468 ms 25928 KB Output is correct
12 Correct 426 ms 24644 KB Output is correct
13 Correct 473 ms 28340 KB Output is correct
14 Correct 201 ms 23544 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 26032 KB Output is correct
2 Correct 509 ms 24604 KB Output is correct
3 Correct 195 ms 28012 KB Output is correct
4 Correct 366 ms 25960 KB Output is correct
5 Correct 455 ms 25992 KB Output is correct
6 Correct 360 ms 25816 KB Output is correct
7 Correct 441 ms 24780 KB Output is correct
8 Correct 175 ms 27984 KB Output is correct
9 Correct 170 ms 23180 KB Output is correct