oj.uz

Submission #523128

# Submission time Handle Problem Language Result Execution time Memory
523128 2022-02-07T06:03:48 Z aadit_ambadkar Poklon (COCI17_poklon7) C++17
48 / 120
 912 ms 208092 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];
    }
    cwe[0]/=2;
    while (cwe[0]) {
        cout << 0;
        cwe[0]/=2;
    }
    cout << "\n";
}

Subtask #1
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94176 KB Output is correct
2 Correct 39 ms 94148 KB Output is correct
3 Correct 39 ms 94208 KB Output is correct
4 Correct 40 ms 94160 KB Output is correct
5 Incorrect 40 ms 94248 KB Output isn't correct
6 Correct 38 ms 94132 KB Output is correct
7 Correct 39 ms 94236 KB Output is correct
8 Correct 47 ms 94164 KB Output is correct
9 Incorrect 40 ms 94288 KB Output isn't correct
10 Correct 40 ms 94272 KB Output is correct
11 Incorrect 46 ms 95192 KB Output isn't correct
12 Incorrect 48 ms 95348 KB Output isn't correct
13 Incorrect 71 ms 99192 KB Output isn't correct
14 Incorrect 106 ms 104168 KB Output isn't correct
15 Incorrect 104 ms 102828 KB Output isn't correct
16 Incorrect 287 ms 126784 KB Output isn't correct
17 Incorrect 614 ms 169572 KB Output isn't correct
18 Incorrect 630 ms 171520 KB Output isn't correct
19 Incorrect 715 ms 185260 KB Output isn't correct
20 Incorrect 912 ms 208092 KB Output isn't correct