답안 #249063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249063 2020-07-14T09:33:51 Z leaked Poklon (COCI17_poklon7) C++14
108 / 120
1000 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];
vector<string*>mx(N);
vector<int>g[N];
pii a[N];
int n;
bool ok;
pii maxx(pii &p1,pii &p2){
    if((*(mx[p1.f])).size()+p1.s>(*(mx[p2.f])).size()+p2.s) return {p1.f,p1.s+1};
    else if((*(mx[p1.f])).size()+p1.s<(*(mx[p2.f])).size()+p2.s) return {p2.f,p2.s+1};
    else{
        for(int i=0;i<min((*(mx[p1.f])).size(),(*(mx[p2.f])).size());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((*(mx[p1.f])).size()<(*(mx[p2.f])).size()){
            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);
            mx[3*i+1]=new string();
            for(int j=32;j>=0;j--){
                if(pw(j) & (-a[i].f)){
                    ok=1;
                    (*(mx[3*i+1])).p_b('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);
            mx[3*i+2]=new string();
            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);
    vector<char> *lol;
    lol=new vector<char>();
    cout<<(*mx[mxp[0].f]);
    for(int j=0;j<mxp[0].s;j++) cout<<0;
    return 0;
}
/*
*/

Compilation message

poklon.cpp: In function 'std::pair<int, int> maxx(std::pair<int, int>&, std::pair<int, int>&)':
poklon.cpp:96:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<min((*(mx[p1.f])).size(),(*(mx[p2.f])).size());i++){
                     ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp: In function 'int main()':
poklon.cpp:167:19: warning: variable 'lol' set but not used [-Wunused-but-set-variable]
     vector<char> *lol;
                   ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 94328 KB Output is correct
2 Correct 52 ms 94336 KB Output is correct
3 Correct 50 ms 94328 KB Output is correct
4 Correct 51 ms 94328 KB Output is correct
5 Correct 49 ms 94328 KB Output is correct
6 Correct 61 ms 94328 KB Output is correct
7 Correct 50 ms 94328 KB Output is correct
8 Correct 52 ms 94328 KB Output is correct
9 Correct 51 ms 94328 KB Output is correct
10 Correct 51 ms 94456 KB Output is correct
11 Correct 61 ms 95992 KB Output is correct
12 Correct 61 ms 96376 KB Output is correct
13 Correct 106 ms 103288 KB Output is correct
14 Correct 153 ms 112248 KB Output is correct
15 Correct 155 ms 109944 KB Output is correct
16 Correct 419 ms 153208 KB Output is correct
17 Correct 893 ms 230636 KB Output is correct
18 Correct 912 ms 233976 KB Output is correct
19 Execution timed out 1110 ms 259324 KB Time limit exceeded
20 Runtime error 1002 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)