Submission #249048

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249048	2020-07-14T08:52:11 Z	Vladikus004	Poklon (COCI17_poklon7)	C++17	114 / 120	719 ms	262148 KB

poklon

#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 1000000 + 3;
int n;
int k0[N];
bool is_p[N];
string s[N];
vector <pii> q;

string to_str(int x){
    string s;
    while (x){
        s += (x % 2) + '0';
        x /= 2;
    }
    reverse(all(s));
    return s;
}

bool bigger(string &s, int sk0, string &t, int tk0){
    if (s.size() + sk0 > t.size() + tk0) return true;
    if (t.size() + tk0 > s.size() + sk0) return false;
    for (int i = 0; i < max(t.size(), s.size()); i++){
        if (i < t.size() && i < s.size()){
            if (s[i] > t[i]) return true;
            if (s[i] < t[i]) return false;
        }else{
            if (i < s.size()){
                if (s[i] == '1') return true;
            }else{
                if (t[i] == '1') return false;
            }
        }
    }
    return false;
}

void dfs(int x){
    if (q[x].first > 0){
        dfs(q[x].first - 1);
    }
    if (q[x].second > 0){
        dfs(q[x].second - 1);
    }
    string s1, s2;
    int k01, k02;
    if (q[x].first > 0) {
        s1 = s[q[x].first - 1];
        k01 = k0[q[x].first - 1];
    }else {
        s1 = to_str(-q[x].first);
        k01 = 0;
    }
    if (q[x].second > 0) {
        s2 = s[q[x].second - 1];
        k02 = k0[q[x].second - 1];
    }else {
        s2 = to_str(-q[x].second);
        k02 = 0;
    }
    if (bigger(s1, k01, s2, k02)) {
        s[x] = s1;
        k0[x] = k01;
    }else {
        s[x] = s2;
        k0[x] = k02;
    }
    k0[x]++;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    q.resize(n);
    for (int i = 0; i < n; i++){
        cin >> q[i].first >> q[i].second;
        if (q[i].first > 0){
            is_p[q[i].first - 1] = true;
        }
        if (q[i].second > 0){
            is_p[q[i].second - 1] = true;
        }
    }
    int st = -1;
    for (int i = 0; i < n; i++){
        if (!is_p[i]){
            st = i;
        }
    }
    dfs(st);
    cout << s[st];
    for (int i = 0; i < k0[st]; i++) cout << 0;
}

Compilation message

poklon.cpp: In function 'bool bigger(std::__cxx11::string&, int, std::__cxx11::string&, int)':
poklon.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < max(t.size(), s.size()); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < t.size() && i < s.size()){
             ~~^~~~~~~~~~
poklon.cpp:30:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < t.size() && i < s.size()){
                             ~~^~~~~~~~~~
poklon.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (i < s.size()){
                 ~~^~~~~~~~~~

Subtask #1

114.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	31616 KB	Output is correct
2	Correct	18 ms	31636 KB	Output is correct
3	Correct	18 ms	31616 KB	Output is correct
4	Correct	18 ms	31616 KB	Output is correct
5	Correct	19 ms	31616 KB	Output is correct
6	Correct	18 ms	31616 KB	Output is correct
7	Correct	18 ms	31616 KB	Output is correct
8	Correct	19 ms	31616 KB	Output is correct
9	Correct	18 ms	31788 KB	Output is correct
10	Correct	19 ms	31744 KB	Output is correct
11	Correct	25 ms	33024 KB	Output is correct
12	Correct	27 ms	33016 KB	Output is correct
13	Correct	54 ms	39032 KB	Output is correct
14	Correct	91 ms	46584 KB	Output is correct
15	Correct	85 ms	37784 KB	Output is correct
16	Correct	267 ms	73464 KB	Output is correct
17	Correct	578 ms	123384 KB	Output is correct
18	Correct	590 ms	131348 KB	Output is correct
19	Correct	692 ms	121848 KB	Output is correct
20	Runtime error	719 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)