oj.uz

Submission #523121

# Submission time Handle Problem Language Result Execution time Memory
523121 2022-02-07T05:58:04 Z aadit_ambadkar Poklon (COCI17_poklon7) C++17
42 / 120
 911 ms 217748 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<int> 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) {
        int 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];});
    int 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 36 ms 86340 KB Output is correct
2 Correct 38 ms 86416 KB Output is correct
3 Correct 37 ms 86416 KB Output is correct
4 Correct 37 ms 86340 KB Output is correct
5 Incorrect 37 ms 86420 KB Output isn't correct
6 Correct 36 ms 86352 KB Output is correct
7 Correct 37 ms 86340 KB Output is correct
8 Correct 38 ms 86436 KB Output is correct
9 Incorrect 40 ms 86424 KB Output isn't correct
10 Incorrect 37 ms 86468 KB Output isn't correct
11 Incorrect 44 ms 87432 KB Output isn't correct
12 Incorrect 45 ms 87648 KB Output isn't correct
13 Incorrect 70 ms 92136 KB Output isn't correct
14 Incorrect 107 ms 98080 KB Output isn't correct
15 Incorrect 98 ms 96652 KB Output isn't correct
16 Incorrect 288 ms 124740 KB Output isn't correct
17 Incorrect 657 ms 175508 KB Output isn't correct
18 Incorrect 727 ms 177576 KB Output isn't correct
19 Incorrect 815 ms 194724 KB Output isn't correct
20 Incorrect 911 ms 217748 KB Output isn't correct