oj.uz

Submission #348829

# Submission time Handle Problem Language Result Execution time Memory
348829 2021-01-15T20:32:07 Z JovanK26 Poklon (COCI17_poklon7) C++14
90 / 120
 43 ms 12396 KB 
#include <bits/stdc++.h>

using namespace std;
int n,m;
int f[200001];
int maks[200001];
vector<int> v[200001];
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
90.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5996 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 5 ms 5868 KB Output is correct
6 Correct 5 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 4 ms 5868 KB Output is correct
10 Correct 4 ms 5868 KB Output is correct
11 Correct 7 ms 6508 KB Output is correct
12 Correct 9 ms 6508 KB Output is correct
13 Correct 24 ms 9196 KB Output is correct
14 Correct 43 ms 12396 KB Output is correct
15 Correct 41 ms 10988 KB Output is correct
16 Runtime error 11 ms 11628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 11 ms 11628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 11 ms 11628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 11 ms 11628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 11 ms 11628 KB Execution killed with signal 11 (could be triggered by violating memory limits)