oj.uz

Submission #152395

# Submission time Handle Problem Language Result Execution time Memory
152395 2019-09-07T21:17:55 Z Leonardo_Paes Poklon (COCI17_poklon7) C++11
120 / 120
 351 ms 42104 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;

int n, a, b, sum;

struct nod{
    int l=0, r=0;
}node[maxn];

void get_max(int newa, int newb){
    int length = 32-__builtin_clz(newa), lengtha = 32-__builtin_clz(a);
    int newsum = length + newb;
    if(newsum>sum){
        a = newa, b = newb, sum = newsum;
    }
    else if(newsum==sum){
        while(length--){
            lengtha--;
            if(newa&(1<<length) and (a&(1<<lengtha))==0){
                a = newa, b = newb, sum = newsum;
                return;
            }
            else if((newa&(1<<length))==0 and a&(1<<lengtha)){
                return;
            }
        }
    }
}

void dfs(int u, int d){
    d++;
    if(node[u].l>0)dfs(node[u].l, d);
    else get_max(-node[u].l, d);
    if(node[u].r>0)dfs(node[u].r, d);
    else get_max(-node[u].r, d);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> node[i].l >> node[i].r;
    }

    dfs(1, 0);

    int length = 32-__builtin_clz(a);

    while(length--)cout << (a&(1<<length)? 1 : 0);

    while(b--)cout << 0;

    cout << "\n";

    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 5 ms 508 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 18 ms 1272 KB Output is correct
14 Correct 33 ms 2168 KB Output is correct
15 Correct 30 ms 1148 KB Output is correct
16 Correct 107 ms 5336 KB Output is correct
17 Correct 246 ms 11456 KB Output is correct
18 Correct 256 ms 12408 KB Output is correct
19 Correct 308 ms 11452 KB Output is correct
20 Correct 351 ms 42104 KB Output is correct