Submission #578056

#	Time	Username	Problem	Language	Result	Execution time	Memory
578056		NintsiChkhaidze	Poklon (COCI17_poklon7)	C++14	120 / 120	288 ms	87376 KiB

poklon

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define s second
#define int ll
#define f first
 
using namespace std;
const int N = 1000005;
int a[N],b[N],cnt[N];

int comp(int a,int add1,int b,int add2){
    int id1=0,id2=0;
    for (int i = 0; i < 30; i++){
        if (((1LL<<i)&a)) id1=i;
        if (((1LL<<i)&b)) id2=i;
    }
    int len1 = id1+1+add1;
    int len2 = id2+1+add2;
    if (len1 > len2) return a;
    if (len2 > len1) return b;
    len1 -= min(add1,add2);
    
    for (int i = 1; i <= len1; i++){
        int a1,b1;
        if (id1<0) a1=0;
        else a1 = ((1LL<<id1)&a);
        
        if (id2<0) b1=0;
        else b1= ((1LL<<id2)&b);
        
        id1--,id2--;
        if (a1 && !b1) return a;
        if (!a1 && b1) return b;
    }
    
    return a;
}
int dfs(int x){
    int mx;
    if (a[x] < 0 && b[x] < 0) {
        mx=max(-a[x],-b[x]);
    }else if (a[x] < 0){
        int k =dfs(b[x]);
        mx=comp(k,cnt[b[x]],-a[x],0);
        if (mx==k) cnt[x]+=cnt[b[x]];
    }else if (b[x]<0){
        int k =dfs(a[x]);
        mx=comp(k,cnt[a[x]],-b[x],0);
        if (mx==k) cnt[x]+=cnt[a[x]];
    }else{
        int p = dfs(a[x]),q=dfs(b[x]);
        mx=comp(p,cnt[a[x]],q,cnt[b[x]]);
        if(mx==p) cnt[x]+=cnt[a[x]];
        else cnt[x]+=cnt[b[x]];
    }
    cnt[x]++;
    return mx;
}
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    cin>>n;
 
    for(int i = 1; i <= n; i++)
        cin>>a[i]>>b[i];
    
    int res = dfs(1);
    bool z=0;
    for (int i=30;i>=0;i--){
        if (((1LL<<i)&res)) z=1,cout<<1;
        else if (z) cout<<0;
    }
    if (z){
        for (int i=1;i<=cnt[1];i++)
            cout<<0;
    }
}

Compilation message (stderr)

poklon.cpp:6: warning: "int" redefined
    6 | #define int ll
      | 
poklon.cpp:2: note: this is the location of the previous definition
    2 | #define int long long
      |

• Subtask 1: 120 / 120