oj.uz

Submission #491803

# Submission time Handle Problem Language Result Execution time Memory
491803 2021-12-04T13:55:59 Z Vladth11 Poklon (COCI17_poklon7) C++14
0 / 120
 1000 ms 172460 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 << " "
 
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] - 1));
    }
    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
0 / 120.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1102 ms 47180 KB Time limit exceeded
2 Execution timed out 1076 ms 47264 KB Time limit exceeded
3 Execution timed out 1102 ms 47200 KB Time limit exceeded
4 Execution timed out 1101 ms 47180 KB Time limit exceeded
5 Execution timed out 1100 ms 47180 KB Time limit exceeded
6 Execution timed out 1093 ms 47260 KB Time limit exceeded
7 Execution timed out 1083 ms 47180 KB Time limit exceeded
8 Execution timed out 1086 ms 47308 KB Time limit exceeded
9 Execution timed out 1089 ms 47308 KB Time limit exceeded
10 Execution timed out 1094 ms 47308 KB Time limit exceeded
11 Execution timed out 1100 ms 48320 KB Time limit exceeded
12 Execution timed out 1100 ms 48332 KB Time limit exceeded
13 Execution timed out 1101 ms 52320 KB Time limit exceeded
14 Execution timed out 1093 ms 57472 KB Time limit exceeded
15 Execution timed out 1068 ms 55104 KB Time limit exceeded
16 Execution timed out 1100 ms 79504 KB Time limit exceeded
17 Execution timed out 1100 ms 121288 KB Time limit exceeded
18 Execution timed out 1092 ms 124168 KB Time limit exceeded
19 Execution timed out 1086 ms 133832 KB Time limit exceeded
20 Execution timed out 1102 ms 172460 KB Time limit exceeded