oj.uz

Submission #523140

# Submission time Handle Problem Language Result Execution time Memory
523140 2022-02-07T06:16:11 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
114 / 120
 938 ms 224792 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<ll, 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 94124 KB Output is correct
2 Correct 39 ms 94160 KB Output is correct
3 Correct 40 ms 94180 KB Output is correct
4 Correct 39 ms 94232 KB Output is correct
5 Incorrect 43 ms 94252 KB Output isn't correct
6 Correct 43 ms 94184 KB Output is correct
7 Correct 40 ms 94176 KB Output is correct
8 Correct 39 ms 94196 KB Output is correct
9 Correct 42 ms 94220 KB Output is correct
10 Correct 39 ms 94268 KB Output is correct
11 Correct 45 ms 95292 KB Output is correct
12 Correct 47 ms 95568 KB Output is correct
13 Correct 77 ms 100036 KB Output is correct
14 Correct 112 ms 105796 KB Output is correct
15 Correct 102 ms 104388 KB Output is correct
16 Correct 296 ms 132164 KB Output is correct
17 Correct 732 ms 182152 KB Output is correct
18 Correct 730 ms 184280 KB Output is correct
19 Correct 798 ms 201156 KB Output is correct
20 Correct 938 ms 224792 KB Output is correct