Submission #491693

#	Time	Username	Problem	Language	Result	Execution time	Memory
491693		Vladth11	Poklon (COCI17_poklon7)	C++14	42 / 120	480 ms	228512 KiB

poklon

#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 / 120