oj.uz

Submission #647694

# Submission time Handle Problem Language Result Execution time Memory
647694 2022-10-03T16:03:23 Z borgar02 Zalmoxis (BOI18_zalmoxis) C++17
50 / 100
 511 ms 75264 KB 
#include <bits/stdc++.h>

using namespace std;
struct node {
    node *ch[2];
    bool marked, vis;
    int h;
    node(int h) : ch({NULL, NULL}), marked(false), vis(false), h(h) {}
    node *go_to(int s) { if(ch[s] == NULL) { ch[!s] = new node(h - 1); return ch[s] = new node(h - 1); } return ch[s]; }
    bool cansplit() { return !ch[0] && !ch[1] && h; }
};
node *root = new node(30);
bool add(int x, int curr = 30, node *t = root)
{
//    cout << curr << "\n";
    if(t -> vis) return false;
    if(curr == x && !(t -> ch[0])) { return t -> vis = t -> marked = true;}
    else if(curr == x) return false;
//    cout << "Going left\n";
    bool ok;
    if(!(ok = add(x, curr - 1, t -> go_to(0)))) {
//        cout << "Going right\n";
        ok = add(x, curr - 1, t -> go_to(1));
    }
    if(!ok) t -> vis = true;
    return ok;
}
const int N = 1e6 + 5;
int a[N];
int k;
int cnt;
void count_leaves(node *t = root)
{
    if(t -> ch[0]) {
        count_leaves(t -> ch[0]);
        count_leaves(t -> ch[1]);
    } else if(!t -> marked) cnt++;
}
void dfs(node *t = root)
{
    if(!t -> ch[0] && !t -> marked && k && t -> cansplit()) {
        k--;
        t -> go_to(0);
    }
    if(t -> ch[0]) {
        dfs(t -> ch[0]);
        dfs(t -> ch[1]);
    }
}
vector <int> res;
void dfs2(node *t = root)
{
    if(t -> ch[0]) {
        dfs2(t -> ch[0]);
        dfs2(t -> ch[1]);
    } else res.push_back(t -> h);
}

int main()
{
    root -> go_to(0);
    int n;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        assert(add(a[i]));
    }
    count_leaves();
    k -= cnt;
    dfs();
    dfs2();
    for(int x : res)
        cout << x << " ";
    return 0;
}

Compilation message

zalmoxis.cpp: In constructor 'node::node(int)':
zalmoxis.cpp:8:67: warning: list-initializer for non-class type must not be parenthesized
    8 |     node(int h) : ch({NULL, NULL}), marked(false), vis(false), h(h) {}
      |                                                                   ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 74956 KB Output is correct
2 Correct 511 ms 75036 KB Output is correct
3 Correct 509 ms 75048 KB Output is correct
4 Correct 504 ms 75060 KB Output is correct
5 Correct 481 ms 75060 KB Output is correct
6 Correct 490 ms 74880 KB Output is correct

Subtask #2
20.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 74880 KB Output is correct
2 Incorrect 477 ms 74916 KB doesn't contain S as a subsequence
3 Incorrect 472 ms 75096 KB doesn't contain S as a subsequence
4 Incorrect 461 ms 74932 KB doesn't contain S as a subsequence
5 Incorrect 492 ms 75264 KB doesn't contain S as a subsequence
6 Incorrect 499 ms 74984 KB doesn't contain S as a subsequence
7 Correct 487 ms 75128 KB Output is correct
8 Correct 478 ms 75168 KB Output is correct
9 Incorrect 423 ms 72484 KB doesn't contain S as a subsequence
10 Incorrect 264 ms 70712 KB doesn't contain S as a subsequence
11 Incorrect 333 ms 71788 KB doesn't contain S as a subsequence
12 Incorrect 166 ms 68880 KB doesn't contain S as a subsequence
13 Incorrect 163 ms 68884 KB doesn't contain S as a subsequence
14 Correct 167 ms 68920 KB Output is correct