Submission #1149097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149097		spycoderyt	Poklon (COCI17_poklon7)	C++20	120 / 120	865 ms	55968 KiB

poklon

#include <bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int> 
using namespace std;
const int N = 1e6+5;
int dp[N][2];
struct node{
    int a,b;
    bool operator < (const node & x) const {
        vector<int> u,v;
        for(int i = 31;i>=0;i--) {
            if(a&(1<<i))u.push_back(i+b);      
            if(x.a&(1<<i))v.push_back(i+x.b);
        }
        for(int i = 0;i<min(u.size(),v.size());i++){
            if(u[i]<v[i])return 1;
            else if(u[i]>v[i])return 0;
        }
        return 1;
    }
    node() : a(0),b(0) {}
    node(int _a,int _b) : a(_a),b(_b) {}
};
node mx;
void dfs(int u,int dep = 0) {
    if(u<0){
        mx = max(mx,node(-u,dep));
    }
    else {
        dfs(dp[u][0],dep+1);
        dfs(dp[u][1],dep+1);
    }
}
int main() {
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++) {
        cin>>dp[i][0]>>dp[i][1];
    }
    dfs(1);
    int yes = 0;
    if(mx.a == 0 && mx.b == 0) {
        cout << 0;
        return 0;
    }
    for(int i = 31;i>=0;i--) {
        if((1<<i)&mx.a){
            yes=1;
            cout<<1;
        } else if(yes) cout << 0;
    }
    for(int i = 0;i<mx.b;i++)cout<<0;
}

/*
main insight: characteristics of the optimal solution

*/

• Subtask 1: 120 / 120