oj.uz

Submission #491799

# Submission time Handle Problem Language Result Execution time Memory
491799 2021-12-04T13:30:16 Z Vladth11 Poklon (COCI17_poklon7) C++14
78 / 120
 1000 ms 172824 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]));
    }
    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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47212 KB Output is correct
2 Correct 27 ms 47296 KB Output is correct
3 Correct 26 ms 47180 KB Output is correct
4 Correct 27 ms 47288 KB Output is correct
5 Incorrect 26 ms 47304 KB Output isn't correct
6 Correct 27 ms 47308 KB Output is correct
7 Correct 27 ms 47196 KB Output is correct
8 Correct 30 ms 47308 KB Output is correct
9 Correct 29 ms 47288 KB Output is correct
10 Correct 25 ms 47316 KB Output is correct
11 Correct 53 ms 48424 KB Output is correct
12 Correct 52 ms 48608 KB Output is correct
13 Correct 703 ms 53180 KB Output is correct
14 Execution timed out 1087 ms 58988 KB Time limit exceeded
15 Correct 74 ms 56672 KB Output is correct
16 Execution timed out 1080 ms 83628 KB Time limit exceeded
17 Execution timed out 1094 ms 127064 KB Time limit exceeded
18 Execution timed out 1063 ms 129696 KB Time limit exceeded
19 Execution timed out 1095 ms 134084 KB Time limit exceeded
20 Execution timed out 1106 ms 172824 KB Time limit exceeded