oj.uz

Submission #348833

# Submission time Handle Problem Language Result Execution time Memory
348833 2021-01-15T20:36:13 Z JovanK26 Poklon (COCI17_poklon7) C++14
114 / 120
 458 ms 126804 KB 
#include <bits/stdc++.h>

using namespace std;
int n,m;
int f[2000010];
int maks[2000010];
vector<int> v[2000010];
void dfs(int node,int dep)
{
    if(node>=n)
    {
        maks[dep]=max(maks[dep],f[node]);
    }
    else
    {
        dfs(v[node][0],dep+1);
        dfs(v[node][1],dep+1);
    }
}
int main()
{
    memset(maks,-1,sizeof(maks));
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a,b;
    cin >> n;
    m=n;
    for(int i=0;i<n;i++)
    {
        cin >> a >> b;
        if(a>0)
        {
            v[i].push_back(a-1);
        }
        else
        {
            f[m]=-a;
            v[i].push_back(m);
            m++;
        }
        if(b>0)
        {
            v[i].push_back(b-1);
        }
        else
        {
            f[m]=-b;
            v[i].push_back(m);
            m++;
        }
    }
    dfs(0,0);
    int rez=-1;
    int rezdep=-1;
    for(int i=0;i<n;i++)
    {
       if(maks[i]==-1)continue;
       bool check=0;
       if(rez==-1)
       {
           check=1;
       }
       else
       {
           int q=(rez+maks[i]-1)/maks[i];
           int pow2=1;
           for(int j=0;j<i-rezdep;j++)
           {
               pow2*=2;
               if(q<=pow2)
               {
                   check=1;
                   break;
               }
           }
       }
       if(check)
       {
           rez=maks[i];
           rezdep=i;
       }
    }
    vector<int> ans;
    for(int i=0;i<rezdep;i++)
    {
        ans.push_back(0);
    }
    while(rez)
    {
        ans.push_back(rez&1);
        rez/=2;
    }
    reverse(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
    {
        cout << ans[i];
    }
    return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<ans.size();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
114.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 33 ms 55148 KB Output is correct
3 Correct 33 ms 55148 KB Output is correct
4 Correct 39 ms 55148 KB Output is correct
5 Correct 33 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 33 ms 55148 KB Output is correct
8 Correct 33 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 33 ms 55148 KB Output is correct
11 Correct 38 ms 55660 KB Output is correct
12 Correct 37 ms 55788 KB Output is correct
13 Correct 52 ms 57708 KB Output is correct
14 Correct 72 ms 60012 KB Output is correct
15 Correct 73 ms 58624 KB Output is correct
16 Correct 167 ms 70248 KB Output is correct
17 Correct 344 ms 89056 KB Output is correct
18 Correct 353 ms 91104 KB Output is correct
19 Correct 428 ms 94588 KB Output is correct
20 Incorrect 458 ms 126804 KB Output isn't correct