제출 #241033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241033		SamAnd	Poklon (COCI17_poklon7)	C++17	120 / 120	571 ms	99200 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1000006;

int n;
int l[N], r[N];

struct ban
{
    ll x;
    int q;
    ban()
    {
        x = 0;
        q = 0;
    }
    ban(ll x, int q)
    {
        this->x = x;
        this->q = q;
    }
};

bool operator>(const ban& a, const ban& b)
{
    int qa = 0, qb = 0;
    ll x = a.x;
    while (x)
    {
        ++qa;
        x /= 2;
    }
    x = b.x;
    while (x)
    {
        ++qb;
        x /= 2;
    }
    if (a.q + qa > b.q + qb)
        return true;
    if (a.q + qa < b.q + qb)
        return false;
    ll ax = a.x;
    ll bx = b.x;
    while (qa < qb)
    {
        ++qa;
        ax *= 2;
    }
    while (qb < qa)
    {
        ++qb;
        bx *= 2;
    }
    return ax > bx;
}

int d[N];
ll s[N];

ban ans;

void dfs(int x)
{
    if (l[x] > 0)
    {
        d[l[x]] = d[x] + 1;
        dfs(l[x]);
        s[x] += s[l[x]];
    }
    else
    {
        s[x] += (-l[x]);
        if (ban(-l[x], d[x] + 1) > ans)
            ans = ban(-l[x], d[x] + 1);
    }
    if (r[x] > 0)
    {
        d[r[x]] = d[x] + 1;
        dfs(r[x]);
        s[x] += s[r[x]];
    }
    else
    {
        s[x] += (-r[x]);
        if (ban(-r[x], d[x] + 1) > ans)
            ans = ban(-r[x], d[x] + 1);
    }
    if (ban(s[x], d[x]) > ans)
        ans = ban(s[x], d[x]);
}

void solv()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &l[i], &r[i]);
    }
    dfs(1);
    vector<int> v;
    while (ans.x)
    {
        v.push_back(ans.x % 2);
        ans.x /= 2;
    }
    reverse(all(v));
    for (int i = 0; i < v.size(); ++i)
        printf("%d", v[i]);
    for (int i = 0; i < ans.q; ++i)
        printf("0");
    printf("\n");
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

컴파일 시 표준 에러 (stderr) 메시지

poklon.cpp: In function 'void solv()':
poklon.cpp:116:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
poklon.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
poklon.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l[i], &r[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 120 / 120