oj.uz

Submission #523124

# Submission time Handle Problem Language Result Execution time Memory
523124 2022-02-07T05:59:20 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
42 / 120
 947 ms 208316 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

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;
        }
        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];
    }
    cout << "\n";
}

Subtask #1
42.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94148 KB Output is correct
2 Correct 42 ms 94148 KB Output is correct
3 Correct 45 ms 94180 KB Output is correct
4 Correct 55 ms 94160 KB Output is correct
5 Incorrect 43 ms 94224 KB Output isn't correct
6 Correct 42 ms 94228 KB Output is correct
7 Correct 40 ms 94152 KB Output is correct
8 Correct 42 ms 94224 KB Output is correct
9 Incorrect 46 ms 94276 KB Output isn't correct
10 Incorrect 42 ms 94276 KB Output isn't correct
11 Incorrect 50 ms 95248 KB Output isn't correct
12 Incorrect 61 ms 95508 KB Output isn't correct
13 Incorrect 74 ms 99680 KB Output isn't correct
14 Incorrect 107 ms 104644 KB Output isn't correct
15 Incorrect 100 ms 103316 KB Output isn't correct
16 Incorrect 343 ms 127288 KB Output isn't correct
17 Incorrect 615 ms 170004 KB Output isn't correct
18 Incorrect 617 ms 171752 KB Output isn't correct
19 Incorrect 752 ms 185296 KB Output isn't correct
20 Incorrect 947 ms 208316 KB Output isn't correct