oj.uz

Submission #491696

# Submission time Handle Problem Language Result Execution time Memory
491696 2021-12-03T21:53:10 Z Vladth11 Poklon (COCI17_poklon7) C++14
6 / 120
 567 ms 236080 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("sse", "sse2", "avx")

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered;

const ll NMAX = 2000001;
const ll nr_of_bits = 17;
const ll MOD = 1000000007;
const ll INF = (1LL << 59);

ll val[NMAX], frunza[NMAX];
vector <int> v[NMAX];
ll cnt, n, maxim = 0;

void addEdge(ll a, ll b){
    if(a < 0){
        val[++cnt] = -a;
        maxim = max(maxim, -a);
        a = cnt;
        frunza[a] = 1;
    }
    v[a].push_back(b);
    v[b].push_back(a);
}

int lvl[NMAX];
int maxi = 0;

void DFS(int node, int p){
    ll maximm = val[node];
    lvl[node] = lvl[p] + 1;
    maxi = max(maxi, lvl[node]);
    ll fii = 0;
    for(auto x : v[node]){
        if(x != p){
            fii++;
            DFS(x, node);
            maximm = max(maximm, val[x]);
        }
    }
    val[node] = max(1LL, fii) * maximm;
}

ll fa(ll x, ll zero){
    ll init = zero;
    for(int i = 0; i <= 30 && zero; i++){
        if(x & (1LL << i))
            break;
        zero--;
    }
    if(zero == 0)
        return x;
    ll nr = 0;
    for(int i = 0; i <= 60; i++){
        if(i < init){
            continue;
        }
        nr += (1LL << i);
    }
    for(int i = 60; i >= init; i--){
        if(nr - (1LL << i) >= x){
            nr -= (1LL << i);
        }
    }
    return nr;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll i;
    cin >> n;
    cnt = n;
    for(i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        addEdge(x, i);
        addEdge(y, i);
    }
    DFS(1, 0);
    for(i = 1; i <= cnt; i++){
        if(!frunza[i])
            continue;
        maxim = max(maxim, fa(val[i], maxi - lvl[i]));
    }
    int ok = 0;
    int last = 0;
    for(int i = 60; i >= 0; i--){
        if(maxim & (1LL << i)){
            ok = 1;
            last = 0;
            cout << 1;
        }else if(ok){
            last++;
            cout << 0;
        }
    }
    for(i = 1; i < maxi - last; i++)
        cout << 0;
    return 0;
}

Subtask #1
6.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47204 KB Output is correct
2 Incorrect 29 ms 47236 KB Output isn't correct
3 Incorrect 21 ms 47256 KB Output isn't correct
4 Incorrect 22 ms 47300 KB Output isn't correct
5 Incorrect 22 ms 47308 KB Output isn't correct
6 Incorrect 21 ms 47228 KB Output isn't correct
7 Incorrect 24 ms 47316 KB Output isn't correct
8 Incorrect 22 ms 47340 KB Output isn't correct
9 Incorrect 22 ms 47268 KB Output isn't correct
10 Incorrect 22 ms 47312 KB Output isn't correct
11 Incorrect 27 ms 48616 KB Output isn't correct
12 Incorrect 35 ms 48708 KB Output isn't correct
13 Incorrect 53 ms 54356 KB Output isn't correct
14 Incorrect 72 ms 61508 KB Output isn't correct
15 Incorrect 75 ms 56692 KB Output isn't correct
16 Incorrect 193 ms 90800 KB Output isn't correct
17 Incorrect 435 ms 146056 KB Output isn't correct
18 Incorrect 448 ms 150836 KB Output isn't correct
19 Incorrect 567 ms 158008 KB Output isn't correct
20 Incorrect 536 ms 236080 KB Output isn't correct