제출 #1266004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266004		nguyenhuythach	Poklon (COCI17_poklon7)	C++20	120 / 120	140 ms	40360 KiB

poklon

//idea from rainboy (and sol on dmoj either lol)
#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax = 1000005;
int n;
int lch[nmax], rch[nmax], mx[nmax];
int st_node[nmax], st_dep[nmax], tp;

void input()
{
    cin >> n;
    FOR(i,1,n) cin >> lch[i] >> rch[i];
}

void solve()
{
    FOR(i,0,n+1) mx[i]=0;
    tp=0;
    st_node[++tp]=1;
    st_dep[tp]=0;
    while(tp)
    {
        int node=st_node[tp];
        int depth=st_dep[tp];
        tp--;
        if(node<=0)
        {
            int mass=-node;
            if(mass>mx[depth]) mx[depth]=mass;
        } 
        else
        {
            st_node[++tp]=rch[node];
            st_dep[tp]=depth+1;
            st_node[++tp]=lch[node];
            st_dep[tp]=depth+1;
        }
    }
    int bestd=0;
    const int TH=60;
    FOR(d,1,n)
    {
        int shifted=(d-bestd>TH)?0:(mx[bestd]>>(d-bestd));
        if(shifted<mx[d]) bestd=d;
    }
    if(mx[bestd] == 0)
    {
        cout << 0 << '\n';
        return;
    }
    int val=mx[bestd];
    string s;
    while(val>0)
    {
        s.push_back(char('0'+(val&1)));
        val>>=1;
    }
    reverse(s.begin(),s.end());
    cout << s;
    FOR(i,1,bestd) cout << '0';
    cout << '\n';
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

• Subtask 1: 120 / 120