oj.uz

Submission #523136

# Submission time Handle Problem Language Result Execution time Memory
523136 2022-02-07T06:12:27 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
114 / 120
 954 ms 209072 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 45 ms 94148 KB Output is correct
2 Correct 41 ms 94148 KB Output is correct
3 Correct 44 ms 94168 KB Output is correct
4 Correct 48 ms 94196 KB Output is correct
5 Incorrect 50 ms 94244 KB Output isn't correct
6 Correct 45 ms 94156 KB Output is correct
7 Correct 47 ms 94132 KB Output is correct
8 Correct 50 ms 94216 KB Output is correct
9 Correct 47 ms 94228 KB Output is correct
10 Correct 44 ms 94308 KB Output is correct
11 Correct 51 ms 95152 KB Output is correct
12 Correct 51 ms 95332 KB Output is correct
13 Correct 92 ms 99268 KB Output is correct
14 Correct 142 ms 104184 KB Output is correct
15 Correct 115 ms 102852 KB Output is correct
16 Correct 340 ms 126800 KB Output is correct
17 Correct 692 ms 169868 KB Output is correct
18 Correct 718 ms 171680 KB Output is correct
19 Correct 808 ms 185396 KB Output is correct
20 Correct 954 ms 209072 KB Output is correct