oj.uz

Submission #408795

# Submission time Handle Problem Language Result Execution time Memory
408795 2021-05-19T16:08:33 Z LptN21 Poklon (COCI17_poklon7) C++14
120 / 120
 469 ms 150212 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
#define oo 1e18
#define eps 1e-9
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
const int N = 3e6+7, M=20+7;
const int MOD = 1e9+7;

int n, m, k, t;

int val[N], d[N];
vector<int> adj[N];

void dfs(int u, int depth=0) {
    if(!sz(adj[u])) d[depth]=max(d[depth], val[u]);
    else dfs(adj[u][0], depth+1), dfs(adj[u][1], depth+1);
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d", &n);
    int u, v, r=n;
    memset(d, -1, sizeof d);
    for(int i=1;i<=n;i++) {
        scanf("%d%d", &u, &v);
        if(u<0) {
            val[++r]=-u;
            adj[i].pb(r);
        } else adj[i].pb(u);
        if(v<0) {
            val[++r]=-v;
            adj[i].pb(r);
        } else adj[i].pb(v);
    }
    dfs(1);vector<int> s;
    int ans=-1, ansdepth=-1;
    for(int i=1;i<N;i++) {
        if(d[i]==-1) continue;
        bool ok=0;
        if(ans<0) ok=1;
        else
            for(int j=1, u=2, r=(ans+d[i]-1)/d[i];j<=i-ansdepth;u<<=1, j++)
                if(u>=r) {ok=1;break;}
        if(ok) ans=d[i], ansdepth=i;
    }
    while(ans) s.pb(ans&1), ans>>=1;
    for(int i=sz(s)-1;i>=0;i--) printf("%d", s[i]);
    for(int i=0;i<ansdepth;i++) printf("0");
    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special cases (n=1?)
    - do smth instead of do nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
poklon.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 82372 KB Output is correct
2 Correct 47 ms 82460 KB Output is correct
3 Correct 46 ms 82372 KB Output is correct
4 Correct 46 ms 82480 KB Output is correct
5 Correct 46 ms 82408 KB Output is correct
6 Correct 47 ms 82388 KB Output is correct
7 Correct 46 ms 82380 KB Output is correct
8 Correct 47 ms 82508 KB Output is correct
9 Correct 50 ms 82528 KB Output is correct
10 Correct 47 ms 82500 KB Output is correct
11 Correct 51 ms 82960 KB Output is correct
12 Correct 58 ms 83164 KB Output is correct
13 Correct 67 ms 85472 KB Output is correct
14 Correct 88 ms 88772 KB Output is correct
15 Correct 86 ms 87756 KB Output is correct
16 Correct 188 ms 100204 KB Output is correct
17 Correct 378 ms 118612 KB Output is correct
18 Correct 381 ms 120168 KB Output is correct
19 Correct 469 ms 121028 KB Output is correct
20 Correct 466 ms 150212 KB Output is correct