Submission #249047

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249047	2020-07-14T08:51:51 Z	Vladikus004	Poklon (COCI17_poklon7)	C++14	114 / 120	748 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	20 ms	31704 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	31636 KB	Output is correct
6	Correct	19 ms	31616 KB	Output is correct
7	Correct	18 ms	31616 KB	Output is correct
8	Correct	18 ms	31728 KB	Output is correct
9	Correct	19 ms	31744 KB	Output is correct
10	Correct	20 ms	31744 KB	Output is correct
11	Correct	25 ms	33024 KB	Output is correct
12	Correct	27 ms	33024 KB	Output is correct
13	Correct	55 ms	38944 KB	Output is correct
14	Correct	91 ms	46584 KB	Output is correct
15	Correct	89 ms	37624 KB	Output is correct
16	Correct	276 ms	73464 KB	Output is correct
17	Correct	604 ms	123492 KB	Output is correct
18	Correct	610 ms	131448 KB	Output is correct
19	Correct	748 ms	121876 KB	Output is correct
20	Runtime error	702 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)