oj.uz

Submission #370705

# Submission time Handle Problem Language Result Execution time Memory
370705 2021-02-24T13:46:01 Z TosakaUCW Poklon (COCI17_poklon7) C++17
120 / 120
 810 ms 135540 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
 
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 1000010
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9
 
using namespace std;
//using namespace __gnu_pbds;
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <int, 6> a6;
 
//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
int L[N], R[N];
 
void tranc(vector <char> &gr, int x)
{
    gr.clear();
 
    while (x > 0)
    {
        if (x % 2) gr.pb('1');
          else gr.pb('0');
 
        x /= 2;
    }
 
    reverse(gr.begin(), gr.end());
}
 
vector <char> dfs(int v)
{
    vector <char> l, r;
 
    if (L[v] < 0) l = dfs(abs(L[v])); else tranc(l, L[v]);
 
    if (R[v] < 0) r = dfs(abs(R[v])); else tranc(r, R[v]);
 
    if (sz(l) < sz(r)) swap(l, r);
 
    if (sz(l) != sz(r)) {l.pb('0'); return l;}
 
    for (int i = 0; i < sz(l); i++)
    {
        if (l[i] == r[i]) continue;
 
        if (r[i] == '1') swap(l, r);
 
        break;
    }
 
    l.pb('0');
 
    return l;
}
 
int main()
{
    //freopen("input.txt", "r", stdin); freopen("output4.txt", "w", stdout);
 
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    int n;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        int l, r;
 
        cin >> l >> r;
 
        if (l < 0) L[i] = abs(l); else L[i] = -l;
 
        if (r < 0) R[i] = abs(r); else R[i] = -r;
    }
 
    vector <char> gr = dfs(1);
 
    for (auto it : gr) cout << it;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 368 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 8 ms 1132 KB Output is correct
12 Correct 10 ms 1004 KB Output is correct
13 Correct 40 ms 4332 KB Output is correct
14 Correct 83 ms 8684 KB Output is correct
15 Correct 75 ms 1260 KB Output is correct
16 Correct 268 ms 21612 KB Output is correct
17 Correct 614 ms 44652 KB Output is correct
18 Correct 625 ms 50924 KB Output is correct
19 Correct 765 ms 34924 KB Output is correct
20 Correct 810 ms 135540 KB Output is correct