oj.uz

Submission #491694

# Submission time Handle Problem Language Result Execution time Memory
491694 2021-12-03T21:03:36 Z Vladth11 Poklon (COCI17_poklon7) C++14
12 / 120
 487 ms 228256 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];
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;
    }
    v[a].push_back(b);
    v[b].push_back(a);
}

int lvl[NMAX];
int maxi = 0;

void DFS(int node, int p){
    ll maxim = 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);
            maxim = max(maxim, val[x]);
        }
    }
    val[node] = max(1LL, fii) * maxim;
}

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);
    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
12.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47276 KB Output is correct
2 Correct 21 ms 47256 KB Output is correct
3 Incorrect 23 ms 47240 KB Output isn't correct
4 Incorrect 24 ms 47164 KB Output isn't correct
5 Incorrect 22 ms 47220 KB Output isn't correct
6 Incorrect 28 ms 47276 KB Output isn't correct
7 Incorrect 23 ms 47176 KB Output isn't correct
8 Incorrect 27 ms 47308 KB Output isn't correct
9 Incorrect 24 ms 47224 KB Output isn't correct
10 Incorrect 25 ms 47268 KB Output isn't correct
11 Incorrect 27 ms 48588 KB Output isn't correct
12 Incorrect 27 ms 48684 KB Output isn't correct
13 Incorrect 43 ms 53844 KB Output isn't correct
14 Incorrect 64 ms 60668 KB Output isn't correct
15 Incorrect 66 ms 55808 KB Output isn't correct
16 Incorrect 211 ms 88076 KB Output isn't correct
17 Incorrect 398 ms 139812 KB Output isn't correct
18 Incorrect 388 ms 144588 KB Output isn't correct
19 Incorrect 487 ms 150096 KB Output isn't correct
20 Incorrect 465 ms 228256 KB Output isn't correct