Submission #491799

#	Time	Username	Problem	Language	Result	Execution time	Memory
491799		Vladth11	Poklon (COCI17_poklon7)	C++14	78 / 120	1106 ms	172824 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 << " "
 
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);
 
int frunza[NMAX], val[NMAX];
vector <int> v[NMAX];
int 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){
    lvl[node] = lvl[p] + 1;
    maxi = max(maxi, lvl[node]);
    for(auto x : v[node]){
        if(x != p){
            DFS(x, node);
        }
    }
}
 
int fa(int x, int zero){
    int 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;
    }
    int 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 / 120