oj.uz

Submission #493288

# Submission time Handle Problem Language Result Execution time Memory
493288 2021-12-10T19:09:53 Z Vladth11 Poklon (COCI17_poklon7) C++14
78 / 120
 1000 ms 166884 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,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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 47216 KB Output is correct
2 Correct 23 ms 47180 KB Output is correct
3 Correct 23 ms 47216 KB Output is correct
4 Correct 27 ms 47288 KB Output is correct
5 Incorrect 25 ms 47292 KB Output isn't correct
6 Correct 24 ms 47280 KB Output is correct
7 Correct 21 ms 47240 KB Output is correct
8 Correct 23 ms 47296 KB Output is correct
9 Correct 24 ms 47248 KB Output is correct
10 Correct 23 ms 47304 KB Output is correct
11 Correct 46 ms 48332 KB Output is correct
12 Correct 55 ms 48552 KB Output is correct
13 Correct 532 ms 52804 KB Output is correct
14 Execution timed out 1089 ms 58228 KB Time limit exceeded
15 Correct 83 ms 56772 KB Output is correct
16 Execution timed out 1091 ms 83344 KB Time limit exceeded
17 Execution timed out 1096 ms 130948 KB Time limit exceeded
18 Execution timed out 1092 ms 133100 KB Time limit exceeded
19 Execution timed out 1073 ms 141764 KB Time limit exceeded
20 Execution timed out 1064 ms 166884 KB Time limit exceeded