oj.uz

Submission #168174

# Submission time Handle Problem Language Result Execution time Memory
168174 2019-12-11T18:43:18 Z sans Poklon (COCI17_poklon7) C++14
48 / 120
 362 ms 103928 KB 
#include <iostream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

#define sp ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
const int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;


struct Node{
    ll lw = -13;
    ll rw = -13;
    ll cl = -13;
    ll cr = -13;
    ll w = 0;
};

vector<Node> node;
ll maxy = 0;

void dfs(int n, int dep){
    if( node[n].cr == -13 ){ node[n].w += node[n].rw; maxy = max(maxy, (1 << (dep+1))*node[n].rw); }
    else{
        dfs(node[n].cr, dep+1);
        node[n].w += node[node[n].cr].w;
    }

    if( node[n].cl == -13 ){ node[n].w += node[n].lw; maxy = max(maxy, (1 << (dep+1))*node[n].lw); }
    else{
        dfs(node[n].cl, dep+1);
        node[n].w += node[node[n].cl].w;
    }
    maxy = max(maxy, (1 << (dep))*node[n].w);
    return;
}

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    ll N;
    cin >> N;
    node.resize(N);

    for(ll i = 0; i < N; ++i){
        ll l, r; cin >> l >> r;

        Node n;
        if(l > 0) n.cl = l-1;
        if(l <= 0) n.lw = -l;
        if(r > 0) n.cr = r-1;
        if(r <= 0) n.rw = -r;

        node[i] = n;
    }

    dfs(0, 0);

    stack<int> bin;
    while(maxy){
        bin.push(maxy%2);
        maxy >>= 1;
    }

    while(!bin.empty()){
        int top = bin.top();
        cout << top;
        bin.pop();
    }
    cout << endl;

    return 0;
}

//cikisir

Subtask #1
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Incorrect 5 ms 1144 KB Output isn't correct
12 Incorrect 6 ms 1144 KB Output isn't correct
13 Incorrect 19 ms 4344 KB Output isn't correct
14 Incorrect 36 ms 8440 KB Output isn't correct
15 Incorrect 35 ms 6084 KB Output isn't correct
16 Incorrect 124 ms 25184 KB Output isn't correct
17 Incorrect 299 ms 57208 KB Output isn't correct
18 Incorrect 294 ms 59640 KB Output isn't correct
19 Incorrect 362 ms 65208 KB Output isn't correct
20 Incorrect 356 ms 103928 KB Output isn't correct