oj.uz

Submission #491693

# Submission time Handle Problem Language Result Execution time Memory
491693 2021-12-03T20:55:27 Z Vladth11 Poklon (COCI17_poklon7) C++14
42 / 120
 480 ms 228512 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(val[1] & (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
42.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47180 KB Output is correct
2 Correct 21 ms 47288 KB Output is correct
3 Correct 22 ms 47180 KB Output is correct
4 Correct 22 ms 47224 KB Output is correct
5 Incorrect 22 ms 47296 KB Output isn't correct
6 Correct 23 ms 47180 KB Output is correct
7 Correct 23 ms 47320 KB Output is correct
8 Correct 23 ms 47300 KB Output is correct
9 Incorrect 23 ms 47256 KB Output isn't correct
10 Incorrect 23 ms 47308 KB Output isn't correct
11 Incorrect 27 ms 48620 KB Output isn't correct
12 Incorrect 28 ms 48844 KB Output isn't correct
13 Incorrect 44 ms 54720 KB Output isn't correct
14 Incorrect 66 ms 62356 KB Output isn't correct
15 Incorrect 66 ms 57432 KB Output isn't correct
16 Incorrect 178 ms 92740 KB Output isn't correct
17 Incorrect 388 ms 144316 KB Output isn't correct
18 Incorrect 392 ms 149156 KB Output isn't correct
19 Incorrect 475 ms 150188 KB Output isn't correct
20 Incorrect 480 ms 228512 KB Output isn't correct