Submission #249055

# Submission time Handle Problem Language Result Execution time Memory
249055 2020-07-14T08:58:51 Z leaked Poklon (COCI17_poklon7) C++14
36 / 120
851 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);
}

string mx[N];
vector<int>p(N,-1);
vector<int>g[N];
pii lol[N];
pii a[N];
ll to[N];
int n;
bool used[N];
void dfs(int v){
    if(!sz(g[v])){
        return ;
    }
    for(auto &z : g[v]){
        dfs(z);
    }
    if(sz(mx[g[v][0]])>sz(mx[g[v][1]])) mx[v]=mx[g[v][0]]+'0';
    else if(sz(mx[g[v][0]])<sz(mx[g[v][1]])) mx[v]=mx[g[v][1]]+'0';
    else{
        for(int i=0;i<sz(mx[g[v][0]]);i++){
            if(mx[g[v][0]][i]>mx[g[v][1]][i]){
                mx[v]=mx[g[v][0]]+'0';
            }
            else if(mx[g[v][0]][i]<mx[g[v][1]][i]) mx[v]=mx[g[v][1]]+'0';
        }
        mx[v]=mx[g[v][1]]+'0';
    }
    mx[g[v][0]].clear();
    mx[g[v][1]].clear();
}
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[0];
    return 0;
}
/*
*/
# Verdict Execution time Memory Grader output
1 Correct 92 ms 176504 KB Output is correct
2 Correct 92 ms 176504 KB Output is correct
3 Correct 93 ms 176504 KB Output is correct
4 Incorrect 95 ms 176504 KB Output isn't correct
5 Correct 103 ms 176504 KB Output is correct
6 Correct 91 ms 176504 KB Output is correct
7 Incorrect 93 ms 176508 KB Output isn't correct
8 Incorrect 96 ms 176632 KB Output isn't correct
9 Incorrect 92 ms 176760 KB Output isn't correct
10 Incorrect 92 ms 176632 KB Output isn't correct
11 Correct 123 ms 201592 KB Output is correct
12 Incorrect 115 ms 191224 KB Output isn't correct
13 Runtime error 186 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 213 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Incorrect 247 ms 193272 KB Output isn't correct
16 Runtime error 431 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 733 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 735 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 851 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 848 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)