oj.uz

Submission #523125

# Submission time Handle Problem Language Result Execution time Memory
523125 2022-02-07T05:59:32 Z aadit_ambadkar Poklon (COCI17_poklon7) C++17
42 / 120
 990 ms 208096 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 40 ms 94148 KB Output is correct
2 Correct 43 ms 94148 KB Output is correct
3 Correct 41 ms 94212 KB Output is correct
4 Correct 40 ms 94236 KB Output is correct
5 Incorrect 42 ms 94176 KB Output isn't correct
6 Correct 48 ms 94196 KB Output is correct
7 Correct 52 ms 94168 KB Output is correct
8 Correct 42 ms 94252 KB Output is correct
9 Incorrect 40 ms 94288 KB Output isn't correct
10 Incorrect 44 ms 94284 KB Output isn't correct
11 Incorrect 49 ms 95156 KB Output isn't correct
12 Incorrect 51 ms 95328 KB Output isn't correct
13 Incorrect 75 ms 99140 KB Output isn't correct
14 Incorrect 114 ms 104148 KB Output isn't correct
15 Incorrect 108 ms 102764 KB Output isn't correct
16 Incorrect 289 ms 126680 KB Output isn't correct
17 Incorrect 620 ms 169604 KB Output isn't correct
18 Incorrect 649 ms 171500 KB Output isn't correct
19 Incorrect 844 ms 185316 KB Output isn't correct
20 Incorrect 990 ms 208096 KB Output isn't correct