oj.uz

Submission #491804

# Submission time Handle Problem Language Result Execution time Memory
491804 2021-12-04T13:57:01 Z Vladth11 Poklon (COCI17_poklon7) C++14
36 / 120
 1000 ms 172420 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;
  	if(zero < 0)
      return x;
    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
36.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47180 KB Output is correct
2 Incorrect 22 ms 47188 KB Output isn't correct
3 Incorrect 23 ms 47348 KB Output isn't correct
4 Correct 23 ms 47180 KB Output is correct
5 Incorrect 22 ms 47180 KB Output isn't correct
6 Incorrect 23 ms 47300 KB Output isn't correct
7 Correct 24 ms 47196 KB Output is correct
8 Incorrect 22 ms 47200 KB Output isn't correct
9 Incorrect 22 ms 47308 KB Output isn't correct
10 Correct 23 ms 47308 KB Output is correct
11 Correct 51 ms 48276 KB Output is correct
12 Incorrect 48 ms 48404 KB Output isn't correct
13 Correct 679 ms 52416 KB Output is correct
14 Execution timed out 1098 ms 57468 KB Time limit exceeded
15 Incorrect 71 ms 55032 KB Output isn't correct
16 Execution timed out 1099 ms 79516 KB Time limit exceeded
17 Execution timed out 1096 ms 121248 KB Time limit exceeded
18 Execution timed out 1105 ms 123956 KB Time limit exceeded
19 Execution timed out 1106 ms 133828 KB Time limit exceeded
20 Execution timed out 1097 ms 172420 KB Time limit exceeded