oj.uz

Submission #523137

# Submission time Handle Problem Language Result Execution time Memory
523137 2022-02-07T06:12:40 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
114 / 120
 896 ms 209124 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]>=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 47 ms 94228 KB Output is correct
2 Correct 55 ms 94184 KB Output is correct
3 Correct 48 ms 94196 KB Output is correct
4 Correct 46 ms 94156 KB Output is correct
5 Incorrect 47 ms 94188 KB Output isn't correct
6 Correct 50 ms 94244 KB Output is correct
7 Correct 46 ms 94204 KB Output is correct
8 Correct 47 ms 94236 KB Output is correct
9 Correct 55 ms 94252 KB Output is correct
10 Correct 48 ms 94308 KB Output is correct
11 Correct 47 ms 95188 KB Output is correct
12 Correct 53 ms 95284 KB Output is correct
13 Correct 82 ms 99180 KB Output is correct
14 Correct 131 ms 104184 KB Output is correct
15 Correct 114 ms 102756 KB Output is correct
16 Correct 304 ms 126816 KB Output is correct
17 Correct 719 ms 169904 KB Output is correct
18 Correct 680 ms 171780 KB Output is correct
19 Correct 745 ms 185356 KB Output is correct
20 Correct 896 ms 209124 KB Output is correct