Submission #249053

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249053	2020-07-14T08:53:42 Z	Vladikus004	Poklon (COCI17_poklon7)	C++17	120 / 120	702 ms	170744 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], k01, k02;
bool is_p[N];
string s[N], s1, s2;
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);
    }
    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

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	31616 KB	Output is correct
2	Correct	19 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	17 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	31744 KB	Output is correct
10	Correct	18 ms	31744 KB	Output is correct
11	Correct	24 ms	32640 KB	Output is correct
12	Correct	34 ms	32640 KB	Output is correct
13	Correct	50 ms	36604 KB	Output is correct
14	Correct	80 ms	41720 KB	Output is correct
15	Correct	80 ms	37564 KB	Output is correct
16	Correct	247 ms	61676 KB	Output is correct
17	Correct	538 ms	99196 KB	Output is correct
18	Correct	546 ms	103160 KB	Output is correct
19	Correct	672 ms	105352 KB	Output is correct
20	Correct	702 ms	170744 KB	Output is correct