oj.uz

Submission #491697

# Submission time Handle Problem Language Result Execution time Memory
491697 2021-12-03T22:05:49 Z Vladth11 Poklon (COCI17_poklon7) C++14
78 / 120
 1000 ms 235052 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;
        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){
        while(init--)
            x /= 2;
        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);
        }
    }
    while(init--)
        nr /= 2;
    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; i++)
        cout << 0;
    return 0;
}

Subtask #1
78.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47172 KB Output is correct
2 Correct 23 ms 47292 KB Output is correct
3 Correct 24 ms 47268 KB Output is correct
4 Correct 24 ms 47180 KB Output is correct
5 Incorrect 23 ms 47180 KB Output isn't correct
6 Correct 24 ms 47304 KB Output is correct
7 Correct 27 ms 47256 KB Output is correct
8 Correct 24 ms 47316 KB Output is correct
9 Correct 24 ms 47308 KB Output is correct
10 Correct 25 ms 47408 KB Output is correct
11 Correct 49 ms 48656 KB Output is correct
12 Correct 44 ms 48716 KB Output is correct
13 Correct 510 ms 54328 KB Output is correct
14 Execution timed out 1088 ms 61380 KB Time limit exceeded
15 Correct 74 ms 56696 KB Output is correct
16 Execution timed out 1087 ms 90636 KB Time limit exceeded
17 Execution timed out 1100 ms 145988 KB Time limit exceeded
18 Execution timed out 1104 ms 150560 KB Time limit exceeded
19 Execution timed out 1098 ms 157748 KB Time limit exceeded
20 Execution timed out 1074 ms 235052 KB Time limit exceeded