oj.uz

Submission #578056

# Submission time Handle Problem Language Result Execution time Memory
578056 2022-06-15T21:05:07 Z NintsiChkhaidze Poklon (COCI17_poklon7) C++14
120 / 120
 288 ms 87376 KB 
#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

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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 4 ms 1036 KB Output is correct
13 Correct 14 ms 3884 KB Output is correct
14 Correct 26 ms 7040 KB Output is correct
15 Correct 27 ms 3576 KB Output is correct
16 Correct 84 ms 17116 KB Output is correct
17 Correct 225 ms 36172 KB Output is correct
18 Correct 200 ms 39104 KB Output is correct
19 Correct 233 ms 35044 KB Output is correct
20 Correct 288 ms 87376 KB Output is correct