Submission #487616

#	Time	Username	Problem	Language	Result	Execution time	Memory
487616		KazamaHoang	Poklon (COCI17_poklon7)	C++14	120 / 120	382 ms	26416 KiB

poklon

#include <bits/stdc++.h>

using namespace std;

void maximize(vector<int>& ans, vector<int>& res) {
    for (int i = 0; i < (int)min(ans.size(), res.size()); ++ i) {
        if (ans[i] != res[i]) {
            if (ans[i] < res[i]) {
                swap(ans, res);
                return;
            }
            if (ans[i] > res[i]) return;
        } 
    }
    if (ans.size() < res.size()) swap(ans, res);
}

int n;
pair<int, int> scale[1000005];
vector<int> ans;
int tmp[30];

void update(int u, int d, int cnt = 0) {
    for (int i = 29; i >= 0; -- i) if ((u >> i) & 1) 
        tmp[++cnt] = i+d;
    vector<int> res(tmp+1, tmp+1+cnt);
    maximize(ans, res);
}

inline void calc() {
    stack<pair<int, int>> st;
    st.push({1, 1});
    while (!st.empty()) {
        int u = st.top().first;
        int d = st.top().second;
        st.pop();
        if (scale[u].first > 0) 
            st.push({scale[u].first, d + 1});
        else update(-scale[u].first, d);

        if (scale[u].second > 0)
            st.push({scale[u].second, d + 1});
        else update(-scale[u].second, d);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++ i) 
        cin >> scale[i].first 
            >> scale[i].second;
    calc();
    ans.push_back(-1);
    for (int j = 0; j + 1 < (int)ans.size(); ++ j) {
        cout << 1;
        for (int h = ans[j] - 1; h > ans[j+1]; -- h) cout << 0;
    }
    return 0;
}

• Subtask 1: 120 / 120