oj.uz

Submission #523129

# Submission time Handle Problem Language Result Execution time Memory
523129 2022-02-07T06:06:45 Z aadit_ambadkar Poklon (COCI17_poklon7) C++17
54 / 120
 945 ms 239432 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<lll> cwe(MX);
vector<lll> 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];});
    lll 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;
    lll 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;
    lll 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
54.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 125508 KB Output is correct
2 Correct 54 ms 125508 KB Output is correct
3 Correct 50 ms 125528 KB Output is correct
4 Correct 54 ms 125516 KB Output is correct
5 Incorrect 53 ms 125508 KB Output isn't correct
6 Correct 50 ms 125468 KB Output is correct
7 Correct 51 ms 125552 KB Output is correct
8 Correct 51 ms 125492 KB Output is correct
9 Incorrect 55 ms 125476 KB Output isn't correct
10 Correct 54 ms 125568 KB Output is correct
11 Incorrect 68 ms 126512 KB Output isn't correct
12 Incorrect 56 ms 126620 KB Output isn't correct
13 Incorrect 82 ms 130504 KB Output isn't correct
14 Incorrect 126 ms 135392 KB Output isn't correct
15 Correct 117 ms 134168 KB Output is correct
16 Incorrect 289 ms 158052 KB Output isn't correct
17 Incorrect 669 ms 200924 KB Output isn't correct
18 Incorrect 652 ms 202680 KB Output isn't correct
19 Incorrect 777 ms 216588 KB Output isn't correct
20 Incorrect 945 ms 239432 KB Output isn't correct