Submission #68131883

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<ll,int>;
const int N=5e5+5;
int n,l[N],r[N];
ll d[N],x[N];
set<pii> s[N*10];
int id[N],tot,rs[N];
void mg(int a,int y)
{
    int x=id[a];
    if(s[x].size()<s[y].size())
    {id[a]=y;swap(x,y);}
    for(auto el:s[y])
    s[x].insert(el);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;n++;d[0]=1;d[1]=1;
    for(int i=2;i<=n;i++)
    cin>>l[i]>>r[i]>>x[i],
    d[i]=min(d[l[i]]+d[r[i]],ll(1e18+7));
    for(int i=0;i<=n;i++)
    {
        id[i]=i;if(i>=2)
        s[i].insert({x[i],i});
    }tot=n;for(int i=n;i>=2;i--)
    {
        if(s[id[i]].empty())continue;
        ll vl=d[l[i]];tot++;
        while(s[id[i]].size())
        {
            auto el=(*s[id[i]].rbegin());
            if(el.first>vl)
            {
                s[id[i]].erase(el);
                s[tot].insert({el.first-vl,el.second});
            }else break;
        }mg(l[i],id[i]),mg(r[i],tot);
    }for(auto [v,t]:s[id[1]])rs[t]=1;
    for(auto [v,t]:s[id[0]])rs[t]=0;
    for(int i=2;i<=n;i++)
    cout<<rs[i]<<'\n';
    return 0;
}

Submission Info

Submission Time
Task G - Binary Cat
User Coffins
Language C++ 17 (Clang 16.0.6)
Score 0
Code Size 1177 Byte
Status TLE
Exec Time 6659 ms
Memory 1245436 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 625
Status
AC × 1
AC × 25
TLE × 29
MLE × 2
Set Name Test Cases
Sample example_00.txt
All example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, random2_00.txt, random2_01.txt, random2_02.txt, random2_03.txt, random2_04.txt, random2_05.txt, random2_06.txt, random2_07.txt, random2_08.txt, random2_09.txt, random2_10.txt, random2_11.txt, random2_12.txt, random2_13.txt, random2_14.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt
Case Name Status Exec Time Memory
example_00.txt AC 121 ms 237872 KiB
hand_00.txt AC 5615 ms 348508 KiB
hand_01.txt AC 5583 ms 317944 KiB
hand_02.txt TLE 6643 ms 346540 KiB
hand_03.txt TLE 6642 ms 313848 KiB
hand_04.txt TLE 6636 ms 283216 KiB
hand_05.txt MLE 5682 ms 1245092 KiB
hand_06.txt TLE 6636 ms 282968 KiB
hand_07.txt MLE 5867 ms 1245436 KiB
hand_08.txt AC 363 ms 315912 KiB
hand_09.txt AC 124 ms 237784 KiB
random2_00.txt TLE 6636 ms 280344 KiB
random2_01.txt TLE 6636 ms 280004 KiB
random2_02.txt TLE 6637 ms 283276 KiB
random2_03.txt TLE 6638 ms 281320 KiB
random2_04.txt TLE 6636 ms 281336 KiB
random2_05.txt TLE 6636 ms 280976 KiB
random2_06.txt TLE 6637 ms 280796 KiB
random2_07.txt TLE 6644 ms 283264 KiB
random2_08.txt TLE 6632 ms 280432 KiB
random2_09.txt TLE 6635 ms 280392 KiB
random2_10.txt TLE 6642 ms 282168 KiB
random2_11.txt TLE 6643 ms 281616 KiB
random2_12.txt TLE 6640 ms 289004 KiB
random2_13.txt TLE 6639 ms 288820 KiB
random2_14.txt TLE 6639 ms 290128 KiB
random_00.txt AC 2459 ms 530312 KiB
random_01.txt TLE 6656 ms 542136 KiB
random_02.txt AC 2550 ms 654728 KiB
random_03.txt AC 2525 ms 660964 KiB
random_04.txt TLE 6652 ms 554808 KiB
random_05.txt AC 2163 ms 525948 KiB
random_06.txt AC 1973 ms 579676 KiB
random_07.txt TLE 6655 ms 605784 KiB
random_08.txt AC 2641 ms 665744 KiB
random_09.txt AC 2594 ms 662872 KiB
random_10.txt TLE 6649 ms 482500 KiB
random_11.txt AC 1994 ms 580808 KiB
random_12.txt AC 2528 ms 655992 KiB
random_13.txt TLE 6659 ms 561604 KiB
random_14.txt AC 2993 ms 661676 KiB
random_15.txt AC 2330 ms 531600 KiB
random_16.txt TLE 6655 ms 515224 KiB
random_17.txt AC 2664 ms 657728 KiB
random_18.txt AC 2785 ms 670644 KiB
random_19.txt TLE 6656 ms 565752 KiB
random_20.txt AC 2563 ms 522784 KiB
random_21.txt AC 1924 ms 572136 KiB
random_22.txt TLE 6656 ms 558432 KiB
random_23.txt AC 2506 ms 655072 KiB
random_24.txt AC 2690 ms 659336 KiB
random_25.txt TLE 6655 ms 483924 KiB
random_26.txt AC 2146 ms 581864 KiB
random_27.txt AC 2649 ms 657216 KiB
random_28.txt TLE 6651 ms 552788 KiB
random_29.txt AC 2420 ms 647132 KiB