oj.uz

Submission #249510

# Submission time Handle Problem Language Result Execution time Memory
249510 2020-07-15T07:37:02 Z ne4eHbKa Poklon (COCI17_poklon7) C++17
120 / 120
 499 ms 158088 KB 
//{ <defines>
#include <bits/stdc++.h>
using namespace std;

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

int md = 998244353;

inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}

int m_bpow(ll A, ll b) {
    int a = A % md;
    ll ans = 1;
    for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
        (ans *= ans) %= md;
        if(p & b)
            (ans *= a) %= md;
    }
    re ans;
}

//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 1e6 + 5;

int n;
list<int> g[N], f[N];

struct I {
    int v, p;
    bool operator< (const I &f) const {
        int a = v, b = f.v, c = f.p - p;
        for(; a < b && c < 0; ++c, a <<= 1);
        for(; a > b && c > 0; --c, b <<= 1);
        re a < b;
    }
    bool operator> (const I &f) const {re f < *this;}
};

I rec(int v) {
    I res = {0, 0};
    for(int i : g[v]) umax(res, rec(i));
    for(int i : f[v]) umax(res, {i, 0});
    res.p++;
    re res;
}

void solve() {
    cin >> n;
    fo(n) g[i].clear(), f[i].clear();
    fo(n) {
        int a, b;
        cin >> a >> b;
        if(a > 1) {
            g[i].pb(a - 1);
        } else {
            f[i].pb(-a);
        }
        if(b > 1) {
            g[i].pb(b - 1);
        } else {
            f[i].pb(-b);
        }
    }
    I z = rec(0);
    string ans = "";
    for(; z.v; z.v >>= 1) ans += char('0' + (z.v & 1));
    reverse(bnd(ans));
    cout << ans;
    fo(z.p) cout << '0';
    cout << endl;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    for(int test = 1; test <= tests; ++test) {
		cerr << "case #" << test << endl;
        solve();
        cerr << endl;
    }
#else
//    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#endif
    return 0;
}

Compilation message

poklon.cpp: In function 'int m_bpow(ll, ll)':
poklon.cpp:50:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47352 KB Output is correct
2 Correct 26 ms 47360 KB Output is correct
3 Correct 27 ms 47360 KB Output is correct
4 Correct 26 ms 47360 KB Output is correct
5 Correct 27 ms 47360 KB Output is correct
6 Correct 26 ms 47360 KB Output is correct
7 Correct 26 ms 47356 KB Output is correct
8 Correct 26 ms 47360 KB Output is correct
9 Correct 26 ms 47360 KB Output is correct
10 Correct 27 ms 47360 KB Output is correct
11 Correct 33 ms 48128 KB Output is correct
12 Correct 32 ms 48256 KB Output is correct
13 Correct 52 ms 51704 KB Output is correct
14 Correct 69 ms 55928 KB Output is correct
15 Correct 72 ms 53496 KB Output is correct
16 Correct 177 ms 74384 KB Output is correct
17 Correct 388 ms 109184 KB Output is correct
18 Correct 383 ms 111852 KB Output is correct
19 Correct 499 ms 118392 KB Output is correct
20 Correct 476 ms 158088 KB Output is correct