Submission #666918

#	Time	Username	Problem	Language	Result	Execution time	Memory
666918		Ahmed57	Poklon (COCI17_poklon7)	C++14	120 / 120	588 ms	197784 KiB

poklon

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>v;
int len[1000001],num[1000001];
int ba[1000001];
string str[1000001];int g = 0;
int dfs(int i){
    if(i<=0){
        long long v = -i , le = 0;
        while(v!=0){
            str[g]+=(v%2)+'0';
            v/=2;
            le++;
        }
        reverse(str[g].begin(),str[g].end());
        len[g] = le;
        num[g] = -i;
        ba[g] = le;
        return g++;
    }
    int le = dfs(v[i-1].first) , ri = dfs(v[i-1].second);
    int w = 0;
    if(len[le]!=len[ri]){
        w = (len[le]>len[ri]?le:ri);
    }else{
        w = (num[le]>num[ri]?le:ri);
    }
    len[w]++;
    return w;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        int a,b;
        cin>>a>>b;
        v.push_back({a,b});
    }
    int ans= dfs(1);
    while(len[ans]>ba[ans]){
        str[ans]+='0';
        len[ans]--;
    }
    cout<<str[ans];
}

• Subtask 1: 120 / 120