oj.uz

Submission #491519

# Submission time Handle Problem Language Result Execution time Memory
491519 2021-12-02T20:47:58 Z Vladth11 Poklon (COCI17_poklon7) C++14
48 / 120
 478 ms 236800 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", "avx")

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);

ll val[NMAX];
vector <int> v[NMAX];
ll cnt, n;

void addEdge(int a, int b){
    if(a < 0){
        val[++cnt] = -a;
        a = cnt;
    }
    v[a].push_back(b);
    v[b].push_back(a);
}

void DFS(int node, int p){
    ll maxim = val[node];
    ll fii = 0;
    for(auto x : v[node]){
        if(x != p){
            fii++;
            DFS(x, node);
            maxim = max(maxim, val[x]);
        }
    }
    val[node] = max(1LL, fii) * maxim;
}

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);
    int ok = 0;
    for(int i = 60; i >= 0; i--){
        if(val[1] & (1LL << i)){
            ok = 1;
            cout << 1;
        }else if(ok){
            cout << 0;
        }
    }
    return 0;
}

Subtask #1
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47172 KB Output is correct
2 Correct 24 ms 47252 KB Output is correct
3 Correct 23 ms 47232 KB Output is correct
4 Correct 24 ms 47288 KB Output is correct
5 Correct 25 ms 47416 KB Output is correct
6 Correct 25 ms 47180 KB Output is correct
7 Correct 23 ms 47180 KB Output is correct
8 Correct 25 ms 47292 KB Output is correct
9 Incorrect 24 ms 47260 KB Output isn't correct
10 Incorrect 26 ms 47360 KB Output isn't correct
11 Incorrect 29 ms 48632 KB Output isn't correct
12 Incorrect 29 ms 48768 KB Output isn't correct
13 Incorrect 45 ms 54212 KB Output isn't correct
14 Incorrect 68 ms 61536 KB Output isn't correct
15 Incorrect 71 ms 56636 KB Output isn't correct
16 Incorrect 177 ms 91096 KB Output isn't correct
17 Incorrect 375 ms 147044 KB Output isn't correct
18 Incorrect 375 ms 152004 KB Output isn't correct
19 Incorrect 478 ms 159380 KB Output isn't correct
20 Incorrect 444 ms 236800 KB Output isn't correct