oj.uz

답안 #523132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523132 2022-02-07T06:09:29 Z aadit_ambadkar Poklon (COCI17_poklon7) C++11
54 / 120
 952 ms 239544 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];
    }
    cwe[0]/=2;
    while (cwe[0]) {
        cout << 0;
        cwe[0]/=2;
    }
    cout << "\n";
}

Subtask #1
54.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 125508 KB Output is correct
2 Correct 53 ms 125508 KB Output is correct
3 Correct 58 ms 125440 KB Output is correct
4 Correct 57 ms 125524 KB Output is correct
5 Incorrect 50 ms 125548 KB Output isn't correct
6 Correct 49 ms 125524 KB Output is correct
7 Correct 52 ms 125452 KB Output is correct
8 Correct 51 ms 125524 KB Output is correct
9 Incorrect 51 ms 125612 KB Output isn't correct
10 Correct 51 ms 125572 KB Output is correct
11 Incorrect 56 ms 126516 KB Output isn't correct
12 Incorrect 71 ms 126696 KB Output isn't correct
13 Incorrect 85 ms 130552 KB Output isn't correct
14 Incorrect 119 ms 135492 KB Output isn't correct
15 Correct 111 ms 134088 KB Output is correct
16 Incorrect 298 ms 158092 KB Output isn't correct
17 Incorrect 658 ms 200872 KB Output isn't correct
18 Incorrect 661 ms 202888 KB Output isn't correct
19 Incorrect 771 ms 216576 KB Output isn't correct
20 Incorrect 952 ms 239544 KB Output isn't correct