Submission #1248817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248817		anha3k25cvp	Poklon (COCI17_poklon7)	C++20	102 / 120	354 ms	267344 KiB

poklon

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const int inf = 7 + 1e9;

int n;
vector <int> a, h;
vector <vector <int>> adj;

void dfs(int u) {
    h[u] = 1;
    vector <int> a_(2), h_(2);
    for (int i = 0; i < 2; i ++) {
        int v = adj[u][i];
        if (v > 0) {
            dfs(v);
            h[u] = max(h[u], h[v] + 1);
            a_[i] = a[v];
            h_[i] = h[v];
        }
        else {
            a_[i] = -v;
            h_[i] = 0;
        }
    }
    if (a_[0] == 0 && a_[1] == 0) {
        a[u] = 0;
        return;
    }
    for (int i = 0; i < 2; i ++)
        if (a_[i] == 0)
            a_[i] = 1;
    if (h_[0] > h_[1]) {
        swap(a_[0], a_[1]);
        swap(h_[0], h_[1]);
    }
    if (h_[1] - h_[0] > 32)
        a[u] = a_[1];
    else {
        for (int i = 0; i < h_[1] - h_[0]; i ++)
            a_[0] /= 2;
        if (h_[0] < h_[1])
            a_[0] |= 1;
        a[u] = max(a_[0], a_[1]);
    }
}

int main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    cin >> n;
    adj.resize(n + 1, vector <int> (2, 0));
    for (int i = 1; i <= n; i ++)
        cin >> adj[i][0] >> adj[i][1];
    a.assign(n + 1, 0);
    h.assign(n + 1, 0);
    dfs(1);
    int check = 0;
    for (int bit = 31; bit >= 0; bit --)
        if ((a[1] >> bit) & 1) {
            check = 1;
            for (int i = bit; i >= 0; i --)
                cout << ((a[1] >> i) & 1);
            break;
        }
    if (check)
        for (int i = 0; i < h[1]; i ++)
            cout << 0;
    return 0;
}

Compilation message (stderr)

poklon.cpp: In function 'int main()':
poklon.cpp:61:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:62:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 102 / 120