oj.uz

Submission #666918

# Submission time Handle Problem Language Result Execution time Memory
666918 2022-11-29T22:07:50 Z Ahmed57 Poklon (COCI17_poklon7) C++14
120 / 120
 588 ms 197784 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 16 ms 31572 KB Output is correct
3 Correct 15 ms 31648 KB Output is correct
4 Correct 15 ms 31572 KB Output is correct
5 Correct 15 ms 31540 KB Output is correct
6 Correct 15 ms 31592 KB Output is correct
7 Correct 18 ms 31632 KB Output is correct
8 Correct 18 ms 31572 KB Output is correct
9 Correct 18 ms 31696 KB Output is correct
10 Correct 15 ms 31712 KB Output is correct
11 Correct 25 ms 32776 KB Output is correct
12 Correct 24 ms 32980 KB Output is correct
13 Correct 44 ms 37704 KB Output is correct
14 Correct 72 ms 44008 KB Output is correct
15 Correct 68 ms 39916 KB Output is correct
16 Correct 204 ms 70068 KB Output is correct
17 Correct 446 ms 119060 KB Output is correct
18 Correct 455 ms 123252 KB Output is correct
19 Correct 578 ms 129836 KB Output is correct
20 Correct 588 ms 197784 KB Output is correct