oj.uz

Submission #523139

# Submission time Handle Problem Language Result Execution time Memory
523139 2022-02-07T06:15:36 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
114 / 120
 954 ms 209252 KB 
/*
    This code belongs to Aadit Ambadkar
    Date: 2022-02-06 21:31:34
    Problem: poklon
*/
#include <bits/stdc++.h>
using namespace::std;

typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define FF first
#define SS second
// typedef __int128 lll;

const int MX = 2e6+3;
vector<int> adj[MX];
vector<ll> cwe(MX);
vector<ll> uw(MX, 0);
vector<ll> dpth(MX);
void gdep(int node, int cdepth, int parent) {
    dpth[node]=cdepth;
    for (auto i : adj[node]) {
        if (i==parent) continue;
        gdep(i, cdepth+1, node);
    }
}
int main() {
    fastio;
    int n; cin >> n;
    if (n==1) {
        int a, b; cin >> a >> b;
        cout << -min(a, b)*2 << "\n";
        return 0;
    }
    map<int, int> mi;
    mi[1]=0;
    FOR(i, 1, n+1) {
        ll a, b; cin >> a >> b;
        if (a>0) {
            mi[a]=2*i-1;
        } else {
            uw[2*i-1] = -a;
        }
        if (b>0) {
            mi[b]=2*i;
        } else {
            uw[2*i] = -b;
        }
        
        adj[mi[i]].pb(2*i-1);
        adj[mi[i]].pb(2*i);
    }
    gdep(0, 0, 0);
    // cout << "CP1" << endl;
    vector<int> v(2*n+1);
    F0R(i, 2*n+1) {
        v[i]=i;
    }
    sort(v.begin(), v.end(), [&](int a, int b) {return dpth[a] > dpth[b];});
    ll cd = dpth[v[0]];
    int p = 0;
    // cout << "CP2" << endl;
    while (p<2*n+1 && dpth[v[p]]==cd) {
        cwe[v[p]]=1;
        p++;
    }
    // cout << "CP3" << endl;
    ll k = 2;
    cd--;
    for (; p < 2*n+1;) {
        if (k>=1e16) break;
        while (p < 2*n+1 && dpth[v[p]]==cd) {
            cwe[v[p]]=k;
            p++;
        }
        cd--;
        k*=2;
    }
    // cout << "CP4" << endl;
    ll ans = 0;
    F0R(i, 2*n+1) {
        if (cwe[i]==0) {
            // cout << i << " ";
            continue;
        }
        if (dpth[v[0]]-dpth[i]>=63) continue;
        ans = max(ans, (cwe[i]+uw[i]-1)/cwe[i]);
    }
    // cout << "\n";
    // ans*=cwe[0];
    vector<int> bits;
    while (ans) {
        bits.pb(ans%2);
        ans/=2;
    }
    R0F(i, bits.size()) {
        cout << bits[i];
    }
    F0R(i, dpth[v[0]]) {
        cout << 0;
    }
    cout << "\n";
}

Subtask #1
114.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 94148 KB Output is correct
2 Correct 43 ms 94148 KB Output is correct
3 Correct 39 ms 94168 KB Output is correct
4 Correct 41 ms 94184 KB Output is correct
5 Incorrect 40 ms 94192 KB Output isn't correct
6 Correct 40 ms 94148 KB Output is correct
7 Correct 40 ms 94172 KB Output is correct
8 Correct 40 ms 94148 KB Output is correct
9 Correct 42 ms 94284 KB Output is correct
10 Correct 42 ms 94284 KB Output is correct
11 Correct 51 ms 95300 KB Output is correct
12 Correct 46 ms 95356 KB Output is correct
13 Correct 72 ms 99180 KB Output is correct
14 Correct 107 ms 104168 KB Output is correct
15 Correct 97 ms 102828 KB Output is correct
16 Correct 307 ms 126872 KB Output is correct
17 Correct 668 ms 169796 KB Output is correct
18 Correct 628 ms 171816 KB Output is correct
19 Correct 731 ms 185428 KB Output is correct
20 Correct 954 ms 209252 KB Output is correct