Submission #249045

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249045	2020-07-14T08:49:38 Z	Vladikus004	Poklon (COCI17_poklon7)	C++14	114 / 120	735 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, is_p[N], k0[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] = 1;
        }
        if (q[i].second > 0){
            is_p[q[i].second - 1] = 1;
        }
    }
    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:27:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < max(t.size(), s.size()); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < t.size() && i < s.size()){
             ~~^~~~~~~~~~
poklon.cpp:28:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < t.size() && i < s.size()){
                             ~~^~~~~~~~~~
poklon.cpp:32: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	31616 KB	Output is correct
3	Correct	18 ms	31616 KB	Output is correct
4	Correct	18 ms	31616 KB	Output is correct
5	Correct	18 ms	31616 KB	Output is correct
6	Correct	19 ms	31616 KB	Output is correct
7	Correct	19 ms	31872 KB	Output is correct
8	Correct	19 ms	31616 KB	Output is correct
9	Correct	18 ms	31744 KB	Output is correct
10	Correct	19 ms	31744 KB	Output is correct
11	Correct	25 ms	33272 KB	Output is correct
12	Correct	28 ms	33280 KB	Output is correct
13	Correct	57 ms	39928 KB	Output is correct
14	Correct	92 ms	48504 KB	Output is correct
15	Correct	89 ms	39416 KB	Output is correct
16	Correct	268 ms	76064 KB	Output is correct
17	Correct	602 ms	127096 KB	Output is correct
18	Correct	623 ms	135004 KB	Output is correct
19	Correct	735 ms	124920 KB	Output is correct
20	Runtime error	702 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)