oj.uz

Submission #251929

# Submission time Handle Problem Language Result Execution time Memory
251929 2020-07-23T06:37:01 Z kartel Poklon (COCI17_poklon7) C++14
0 / 120
 1000 ms 145996 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;

pair <int, int> f[N];
int i, n;

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;
}

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;
}

psi rec(ll v)
{
    psi lF;
    psi rF;

    if (f[v].S > 0) lF = rec(f[v].F); else lF = {bin(-f[v].F), 0};
    if (f[v].S > 0) rF = rec(f[v].S); else rF = {bin(-f[v].S), 0};

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


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++)
    {
        int l, r;
        cin >> l >> r;
        f[i] = {l, r};
    }

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

Subtask #1
0 / 120.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 123604 KB Time limit exceeded
2 Execution timed out 1096 ms 123616 KB Time limit exceeded
3 Execution timed out 1101 ms 123744 KB Time limit exceeded
4 Execution timed out 1097 ms 123620 KB Time limit exceeded
5 Execution timed out 1096 ms 123788 KB Time limit exceeded
6 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Execution timed out 1098 ms 123616 KB Time limit exceeded
8 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Execution timed out 1105 ms 123612 KB Time limit exceeded
10 Execution timed out 1105 ms 123744 KB Time limit exceeded
11 Execution timed out 1100 ms 123920 KB Time limit exceeded
12 Execution timed out 1087 ms 123908 KB Time limit exceeded
13 Runtime error 15 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Execution timed out 1096 ms 124644 KB Time limit exceeded
15 Runtime error 29 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Execution timed out 1095 ms 126204 KB Time limit exceeded
17 Execution timed out 1098 ms 129856 KB Time limit exceeded
18 Execution timed out 1087 ms 129944 KB Time limit exceeded
19 Execution timed out 1098 ms 131404 KB Time limit exceeded
20 Execution timed out 1096 ms 145996 KB Time limit exceeded