oj.uz

Submission #348830

# Submission time Handle Problem Language Result Execution time Memory
348830 2021-01-15T20:33:06 Z JovanK26 Poklon (COCI17_poklon7) C++14
114 / 120
 470 ms 144084 KB 
#include <bits/stdc++.h>

using namespace std;
int n,m;
int f[2000001];
int maks[2000001];
vector<int> v[2000001];
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 35 ms 55148 KB Output is correct
2 Correct 33 ms 55148 KB Output is correct
3 Correct 35 ms 55148 KB Output is correct
4 Correct 33 ms 55148 KB Output is correct
5 Correct 34 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 34 ms 55148 KB Output is correct
11 Correct 37 ms 55660 KB Output is correct
12 Correct 38 ms 55660 KB Output is correct
13 Correct 54 ms 57608 KB Output is correct
14 Correct 74 ms 60140 KB Output is correct
15 Correct 69 ms 58732 KB Output is correct
16 Correct 167 ms 75924 KB Output is correct
17 Correct 345 ms 102880 KB Output is correct
18 Correct 352 ms 104928 KB Output is correct
19 Correct 435 ms 111972 KB Output is correct
20 Incorrect 470 ms 144084 KB Output isn't correct