oj.uz

Submission #523134

# Submission time Handle Problem Language Result Execution time Memory
523134 2022-02-07T06:11:12 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
114 / 120
 992 ms 209140 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;
    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;) {
        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]>=32) 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 46 ms 94168 KB Output is correct
2 Correct 40 ms 94128 KB Output is correct
3 Correct 45 ms 94232 KB Output is correct
4 Correct 39 ms 94132 KB Output is correct
5 Incorrect 47 ms 94148 KB Output isn't correct
6 Correct 41 ms 94184 KB Output is correct
7 Correct 41 ms 94252 KB Output is correct
8 Correct 43 ms 94148 KB Output is correct
9 Correct 41 ms 94200 KB Output is correct
10 Correct 43 ms 94232 KB Output is correct
11 Correct 50 ms 95232 KB Output is correct
12 Correct 59 ms 95340 KB Output is correct
13 Correct 77 ms 99200 KB Output is correct
14 Correct 108 ms 104264 KB Output is correct
15 Correct 98 ms 102744 KB Output is correct
16 Correct 325 ms 126928 KB Output is correct
17 Correct 612 ms 169880 KB Output is correct
18 Correct 633 ms 171800 KB Output is correct
19 Correct 738 ms 185496 KB Output is correct
20 Correct 992 ms 209140 KB Output is correct