oj.uz

Submission #523133

# Submission time Handle Problem Language Result Execution time Memory
523133 2022-02-07T06:10:34 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
108 / 120
 1000 ms 240524 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;
        }
        if (dpth[v[0]]-dpth[i]>=32) 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
108.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125488 KB Output is correct
2 Correct 50 ms 125504 KB Output is correct
3 Correct 51 ms 125508 KB Output is correct
4 Correct 50 ms 125540 KB Output is correct
5 Incorrect 49 ms 125536 KB Output isn't correct
6 Correct 48 ms 125516 KB Output is correct
7 Correct 52 ms 125516 KB Output is correct
8 Correct 56 ms 125508 KB Output is correct
9 Correct 50 ms 125516 KB Output is correct
10 Correct 52 ms 125600 KB Output is correct
11 Correct 56 ms 126528 KB Output is correct
12 Correct 60 ms 126624 KB Output is correct
13 Correct 82 ms 130456 KB Output is correct
14 Correct 122 ms 135512 KB Output is correct
15 Correct 123 ms 134112 KB Output is correct
16 Correct 298 ms 158248 KB Output is correct
17 Correct 661 ms 201104 KB Output is correct
18 Correct 647 ms 203096 KB Output is correct
19 Correct 748 ms 216852 KB Output is correct
20 Execution timed out 1055 ms 240524 KB Time limit exceeded