제출 #1268654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268654		nhphuc	Poklon (COCI17_poklon7)	C++20	120 / 120	330 ms	204728 KiB

poklon

#include <bits/stdc++.h>
using namespace std;

struct big {

    int v, sh;

    big (int x, int y):
        v(x), sh(y){}

    bool operator< (const big &oth) const {
        if (sh - oth.sh > 30){
            return false;
        } else
        if (oth.sh - sh > 30){
            return true;
        } else {
            if (sh > oth.sh){
                return (1ll * v * (1ll << (sh - oth.sh)) < 1ll * oth.v);
            } else {
                return (1ll * v < 1ll * oth.v * (1ll << (oth.sh - sh)));
            }
        }
    }

};

const int N = 1000100;

int n, res[N];
vector<int> adj[N];
vector<big> chd[N];

big dfs (int u){
    for (int v : adj[u]){
        chd[u].push_back(dfs(v));
    }
    sort(chd[u].begin(), chd[u].end());
    chd[u].back().sh += 1;
    return chd[u].back();
}

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        int x, y; cin >> x >> y;
        if (x > 0){
            adj[i].push_back(x);
        } else {
            if (x != 0){
                chd[i].push_back(big(-x, 0));
            }
        }
        if (y > 0){
            adj[i].push_back(y);
        } else {
            if (y != 0){
                chd[i].push_back(big(-y, 0));
            }
        }
    }
    big ans = dfs(1);
    for (int i = 0; i <= 30; ++i){
        if (ans.v & (1 << i)){
            res[i + ans.sh] = 1;
        }
    }
    for (int i = N - 1; i >= 0; --i){
        if (res[i]){
            for (int j = i; j >= 0; --j){
                cout << res[j];
            }
            return 0;
        }
    }
}

• Subtask 1: 120 / 120