답안 #539149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
539149 2022-03-18T13:41:10 Z Soul234 Poklon (COCI17_poklon7) C++14
120 / 120
710 ms 143992 KB
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a = b,1 : 0;
}

const int MX = 2e6+10;
int best[MX], N, w[MX], ind;
vi adj[MX];

void dfs(int u, int dep) {
    if(u>=N) {
        ckmax(best[dep], w[u]);
        return;
    }
    dfs(adj[u][0], dep+1);
    dfs(adj[u][1], dep+1);
}

void solve() {
    memset(best,-1, sizeof best);
    cin>>N;
    ind = N;
    F0R(i,N) {
        int a, b;
        cin>>a>>b;
        if(a>0) {
            adj[i].pb(a-1);
        }
        else {
            w[ind] = -a;
            adj[i].pb(ind++);
        }
        if(b>0) {
            adj[i].pb(b-1);
        }
        else {
            w[ind] = -b;
            adj[i].pb(ind++);
        }
    }
    dfs(0,0);
    int res, res_dep; res = res_dep = -1;
    F0R(i,MX) if(~best[i]) {
        bool ok = false;
        if(res == -1) {
            ok = true;
        }
        else {
            int tmp = (res + best[i] -1)/best[i];
            int pw2 = 1;
            F0R(_,i-res_dep) {
                pw2 = pw2*2;
                if(tmp <= pw2) {
                    ok = true;
                    break;
                }
            }
        }
        if(ok) {
            res = best[i];
            res_dep = i;
        }
    }
    vi ans;
    F0R(_,res_dep) ans.pb(0);
    while(res>0) ans.pb(res&1), res>>=1;
    reverse(all(ans));
    each(e,ans) cout << e;
    cout << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

poklon.cpp: In function 'void setIO(std::string)':
poklon.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 55020 KB Output is correct
2 Correct 33 ms 55224 KB Output is correct
3 Correct 34 ms 55108 KB Output is correct
4 Correct 38 ms 55048 KB Output is correct
5 Correct 41 ms 55128 KB Output is correct
6 Correct 43 ms 54988 KB Output is correct
7 Correct 41 ms 55000 KB Output is correct
8 Correct 40 ms 55100 KB Output is correct
9 Correct 34 ms 55112 KB Output is correct
10 Correct 36 ms 55172 KB Output is correct
11 Correct 44 ms 55752 KB Output is correct
12 Correct 46 ms 55752 KB Output is correct
13 Correct 68 ms 58336 KB Output is correct
14 Correct 91 ms 61544 KB Output is correct
15 Correct 78 ms 60176 KB Output is correct
16 Correct 171 ms 75824 KB Output is correct
17 Correct 427 ms 102764 KB Output is correct
18 Correct 388 ms 104880 KB Output is correct
19 Correct 471 ms 111888 KB Output is correct
20 Correct 710 ms 143992 KB Output is correct