oj.uz

Submission #251924

# Submission time Handle Problem Language Result Execution time Memory
251924 2020-07-23T06:31:42 Z kartel Poklon (COCI17_poklon7) C++14
108 / 120
 1000 ms 262148 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,nso-stack-protector,unroll-loops,fast-math,-O3")
#define F first
#define S second
#define pb push_back
#define N +1000500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define Max_A int(1e9)
//#define el endl
#define pii pair <int, int>
#define psi pair <string, int>
#define err ld(1e-9)
#define Max_S int(3e6)
#define last(x) x.back()
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

struct str{
    string l, r;
    int le, ri;
};

str f[N];
ll i, n, ans;

psi umax(psi a, psi b)
{
    if (sz(a.F) + a.S > sz(b.F) + b.S) return a;
    if (sz(a.F) + a.S < sz(b.F) + b.S) return b;

    string na = a.F, nb = b.F;

    while (sz(na) < sz(nb)) na += "0";
    while (sz(na) > sz(nb)) nb += "0";

    int i = 0;
    while (i < sz(na) && na[i] == nb[i]) i++;

    if (i == sz(na)) return a;

    if (na[i] > nb[i]) return a;
                  else return b;
}

psi upd(psi x)
{
    x.S++;
    return x;
}

psi rec(ll v)
{
    psi lF = {f[v].l, 0};
    psi rF = {f[v].r, 0};

    if (f[v].le != 0) lF = rec(f[v].le);
    if (f[v].ri != 0) rF = rec(f[v].ri);

    return upd(umax(lF, rF));
}

string bin(ll x)
{
    string ans = "";
    while (x)
    {
        if (x & 1)
            ans += "1";
        else ans += "0";
        //ans += char('0' + x & 1);
        x >>= 1;
    }
    reverse(all(ans));
    return ans;
}

string restore(psi x)
{
    string ans = x.F;
    for (int i = 0; i < x.S; i++) ans += "0";
    return ans;
}

int main()
{
    cout.precision(2);
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        ll l, r;
        cin >> l >> r;
        if (l > 0) f[i].le = l; else f[i].l = bin(-l);
        if (r > 0) f[i].ri = r; else f[i].r = bin(-r);
    }

    cout << restore(rec(1)) << el;
}
//
//00000
//00110
//00111
//00011
//00000

Subtask #1
108.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70784 KB Output is correct
2 Correct 37 ms 70784 KB Output is correct
3 Correct 36 ms 70776 KB Output is correct
4 Correct 39 ms 70776 KB Output is correct
5 Correct 38 ms 70836 KB Output is correct
6 Correct 37 ms 70784 KB Output is correct
7 Correct 36 ms 70784 KB Output is correct
8 Correct 37 ms 70784 KB Output is correct
9 Correct 37 ms 70912 KB Output is correct
10 Correct 38 ms 70904 KB Output is correct
11 Correct 49 ms 72824 KB Output is correct
12 Correct 51 ms 72440 KB Output is correct
13 Correct 90 ms 80760 KB Output is correct
14 Correct 145 ms 91512 KB Output is correct
15 Correct 140 ms 75512 KB Output is correct
16 Correct 419 ms 124664 KB Output is correct
17 Correct 860 ms 185976 KB Output is correct
18 Correct 869 ms 199656 KB Output is correct
19 Execution timed out 1062 ms 171384 KB Time limit exceeded
20 Runtime error 882 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)