Submission #249059

# Submission time Handle Problem Language Result Execution time Memory
249059 2020-07-14T09:15:15 Z leaked Poklon (COCI17_poklon7) C++14
96 / 120
876 ms 262148 KB
#include<bits/stdc++.h>
using namespace std;
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cout << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cout << endl; }
eni(!=) cout << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fi first
#define f first
#define se second
#define s second
#define vi_a vector<int>a;
#define p_b push_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ll long long
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define getfiles    ifstream cin("input.txt");ofstream cout("output.txt");
#define pw(x) (1ll << x)
#define sz(x) (ll)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
#define len(a) (ll)a.size()
#define rep(x,l,r) for(ll x=l;x<r;x++)

//using namespace __gnu_pbds;
ld eps = (ld)1 / 1e6;
const ld pi=3.14159265359;
ll inf = 1e18,mod1=1e9+7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
void binary(ll val,int to) {for(int i=0;i<to;i++) cerr<<(pw(i) & val ? 1 : 0); cerr<<endl;}
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const ll R=1e4;
const ll tx[4]={1,0,-1,0};
const ll ty[4]={0,1,0,-1};
const char rev_to[4]={'E','W','N','S'};
const char o[4]={'S','P','R'};
const int N=3e6+1;
const int M=1e9+7;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> st;
void bad(){
    cout<<-1;
    exit(0);
}
pii mxp[N];
string mx[N];
vector<int>g[N];
pii a[N];
int n;
bool ok;
pii maxx(pii p1,pii p2){
   // string c;
    if(sz(mx[p1.f])+p1.s>sz(mx[p2.f])+p2.s) return {p1.f,p1.s+1};
    else if(sz(mx[p1.f])+p1.s<sz(mx[p2.f])+p2.s) return {p2.f,p2.s+1};
    else{
        for(int i=0;i<min(sz(mx[p1.f]),sz(mx[p2.f]));i++){
            if(mx[p1.f][i]>mx[p2.f][i]){
                return {p1.f,p1.s+1};
            }
            else if(mx[p1.f][i]<mx[p2.f][i]) return {p2.f,p2.s+1};
        }
        if(sz(mx[p1.f])<sz(mx[p2.f])){
            return {p2.f,p2.s+1};
        }
        else{
            return {p1.f,p1.s+1};
        }
    }
}
void dfs(int v){
    ///  debug()<<imie(mx[v])<<imie(v);
    if(!sz(g[v])){
        mxp[v]={v,0};
        return ;
    }
    for(auto &z : g[v]){
        dfs(z);
    }
    ok=0;
    mxp[v]=maxx(mxp[g[v][0]],mxp[g[v][1]]);
}
signed main()
{
    fast_io;
    ///TODO :
    cin>>n;
   // int a,b;
   bool ok=1;
    for(int i=0;i<n;i++){
        cin>>a[i].f>>a[i].s;
        if(a[i].f>0){
            g[3*i].p_b(3*(a[i].f-1));
        }
        else{
            ok=0;
            g[3*i].p_b(3*i+1);
            for(int j=32;j>=0;j--){
                if(pw(j) & (-a[i].f)){
                    ok=1;
                    mx[3*i+1]+='1';
                }
                else{
                    if(ok)  mx[3*i+1]+='0';
                }
            }
        }
        if(a[i].s>0){
            g[3*i].p_b(3*(a[i].s-1));
        }
        else{
            ok=0;
            g[3*i].p_b(3*i+2);
            for(int j=32;j>=0;j--){
                if(pw(j) & (-a[i].s)){
                    ok=1;
                    mx[3*i+2]+='1';
                }
                else{
                    if(ok)  mx[3*i+2]+='0';
                }
            }
        }
    }
    dfs(0);
    cout<<mx[mxp[0].f];
    for(int j=0;j<mxp[0].s;j++) cout<<0;
    return 0;
}
/*
*/
# Verdict Execution time Memory Grader output
1 Correct 89 ms 164728 KB Output is correct
2 Correct 92 ms 164728 KB Output is correct
3 Correct 84 ms 164728 KB Output is correct
4 Correct 89 ms 164728 KB Output is correct
5 Correct 91 ms 164860 KB Output is correct
6 Correct 88 ms 164728 KB Output is correct
7 Correct 86 ms 164728 KB Output is correct
8 Correct 86 ms 164728 KB Output is correct
9 Correct 91 ms 164728 KB Output is correct
10 Correct 89 ms 164856 KB Output is correct
11 Correct 94 ms 166008 KB Output is correct
12 Correct 97 ms 166264 KB Output is correct
13 Correct 131 ms 171384 KB Output is correct
14 Correct 192 ms 177968 KB Output is correct
15 Correct 183 ms 175740 KB Output is correct
16 Correct 411 ms 207736 KB Output is correct
17 Runtime error 744 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 740 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 876 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 850 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)