oj.uz

Submission #249038

# Submission time Handle Problem Language Result Execution time Memory
249038 2020-07-14T08:35:55 Z Vladikus004 Poklon (COCI17_poklon7) C++14
78 / 120
 646 ms 262148 KB 
#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];
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, string &t){
    if (s.size() > t.size()) return true;
    if (t.size() > s.size()) return false;
    for (int i = 0; i < s.size(); i++){
        if (s[i] > t[i]) return true;
        if (s[i] < t[i]) 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;
    if (q[x].first > 0) s1 = s[q[x].first - 1];
    else s1 = to_str(-q[x].first);
    if (q[x].second > 0) s2 = s[q[x].second - 1];
    else s2 = to_str(-q[x].second);
//    cout << x << " : " << s1 << " " << s2 << "  -  ";
    if (bigger(s1, s2)) s[x] = s1 ;
    else s[x] = s2;
    s[x] += '0';
//    cout << s[x] << "\n";
}

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];
}

Compilation message

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

Subtask #1
78.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 19 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 19 ms 31616 KB Output is correct
8 Correct 21 ms 31616 KB Output is correct
9 Correct 19 ms 31864 KB Output is correct
10 Correct 23 ms 31744 KB Output is correct
11 Correct 41 ms 55672 KB Output is correct
12 Correct 36 ms 45184 KB Output is correct
13 Runtime error 198 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 229 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Correct 100 ms 41208 KB Output is correct
16 Runtime error 330 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 539 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 516 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 646 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 398 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)