Submission #249046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249046	2020-07-14T08:51:22 Z	Vladikus004	Poklon (COCI17_poklon7)	C++14	84 / 120	729 ms	261624 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;
short 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

84.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	19 ms	31616 KB	Output is correct
4	Correct	18 ms	31744 KB	Output is correct
5	Correct	19 ms	31608 KB	Output is correct
6	Correct	18 ms	31616 KB	Output is correct
7	Correct	19 ms	31616 KB	Output is correct
8	Correct	19 ms	31616 KB	Output is correct
9	Correct	19 ms	31744 KB	Output is correct
10	Correct	19 ms	31744 KB	Output is correct
11	Correct	25 ms	33024 KB	Output is correct
12	Correct	29 ms	32944 KB	Output is correct
13	Correct	57 ms	38904 KB	Output is correct
14	Incorrect	111 ms	46424 KB	Output isn't correct
15	Correct	99 ms	37496 KB	Output is correct
16	Incorrect	261 ms	72568 KB	Output isn't correct
17	Incorrect	619 ms	121464 KB	Output isn't correct
18	Incorrect	599 ms	129604 KB	Output isn't correct
19	Incorrect	718 ms	119932 KB	Output isn't correct
20	Incorrect	729 ms	261624 KB	Output isn't correct