oj.uz

Submission #491698

# Submission time Handle Problem Language Result Execution time Memory
491698 2021-12-03T22:07:00 Z Vladth11 Poklon (COCI17_poklon7) C++14
78 / 120
 1000 ms 235124 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 <= 30; i++){
        if(i < init){
            continue;
        }
        nr += (1LL << i);
    }
    for(int i = 30; 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 = 30; 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 21 ms 47180 KB Output is correct
2 Correct 21 ms 47224 KB Output is correct
3 Correct 22 ms 47216 KB Output is correct
4 Correct 24 ms 47260 KB Output is correct
5 Incorrect 22 ms 47280 KB Output isn't correct
6 Correct 22 ms 47180 KB Output is correct
7 Correct 25 ms 47308 KB Output is correct
8 Correct 26 ms 47308 KB Output is correct
9 Correct 22 ms 47388 KB Output is correct
10 Correct 22 ms 47348 KB Output is correct
11 Correct 51 ms 48616 KB Output is correct
12 Correct 48 ms 48744 KB Output is correct
13 Correct 518 ms 54328 KB Output is correct
14 Execution timed out 1101 ms 61444 KB Time limit exceeded
15 Correct 100 ms 56672 KB Output is correct
16 Execution timed out 1098 ms 90664 KB Time limit exceeded
17 Execution timed out 1106 ms 145664 KB Time limit exceeded
18 Execution timed out 1091 ms 150512 KB Time limit exceeded
19 Execution timed out 1101 ms 157648 KB Time limit exceeded
20 Execution timed out 1097 ms 235124 KB Time limit exceeded