oj.uz

Submission #523138

# Submission time Handle Problem Language Result Execution time Memory
523138 2022-02-07T06:14:11 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
114 / 120
 997 ms 209108 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;) {
        if (k>=1e16) break;
        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 46 ms 94404 KB Output is correct
2 Correct 39 ms 94148 KB Output is correct
3 Correct 44 ms 94196 KB Output is correct
4 Correct 40 ms 94156 KB Output is correct
5 Incorrect 51 ms 94148 KB Output isn't correct
6 Correct 41 ms 94180 KB Output is correct
7 Correct 42 ms 94192 KB Output is correct
8 Correct 38 ms 94252 KB Output is correct
9 Correct 42 ms 94228 KB Output is correct
10 Correct 41 ms 94288 KB Output is correct
11 Correct 47 ms 95148 KB Output is correct
12 Correct 47 ms 95304 KB Output is correct
13 Correct 76 ms 99244 KB Output is correct
14 Correct 109 ms 104200 KB Output is correct
15 Correct 98 ms 102740 KB Output is correct
16 Correct 309 ms 126868 KB Output is correct
17 Correct 677 ms 169844 KB Output is correct
18 Correct 624 ms 171712 KB Output is correct
19 Correct 725 ms 185364 KB Output is correct
20 Correct 997 ms 209108 KB Output is correct