Submission #19541346


Source Code Expand

Copy
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan Choudhary (@aryanc403)
*/

#ifdef ARYANC403
    #include "/home/aryan/codes/PastCodes/template/header.h"
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    #pragma GCC optimize ("-ffloat-store")
    #include<iostream>
    #include<bits/stdc++.h>
    #define dbg(args...)
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;


const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vector<vi> e;
    lli A,B;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

lli dfs(lli u,lli p)
{
    vi b;
    lli cnt=0;
    for(auto x:e[u])
    {
        if(x==p)
            continue;
        b.pb(dfs(x,u));
        cnt++;
    }
    dbg(u,p,e[u],b);
    A+=cnt/2;
    if(sz(b)%2==0)
        b.pb(0);
    sort(all(b));

    if(b.back()>B)
        A=INF;
    auto chk=[b,B](const lli m)-> bool {
        lli i=0,j=sz(b)-1;
        if(i==m)
            i++;
        if(j==m)
            j--;
        while(i<j)
        {
            if(b[i]+b[j]>B)
                return false;
            i++;j--;
            if(i==m)
                i++;
            if(j==m)
                j--;
        }
        return true;
    };
    lli l=-1,r=sz(b);
    while(r-l>1)
    {
        const lli m=(r+l)/2;
        if(chk(m))
            r=m;
        else
            l=m;
    }
    if(r==sz(b))
    {
        r--;
        A=INF;
    }
    return b[r]+1;
}

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// cin>>T;while(T--)
{

    cin>>n;
    e.resize(n);
    fo(i,n-1)
    {
        cin>>u>>v;
        u--;v--;
        e[u].pb(v);
        e[v].pb(u);
    }

    if(n==2)
    {
        cout<<"1 1"<<endl;
        return 0;
    }

    lli rt=0;
    fo(rt,n)
    {
        if(sz(e[rt])!=1)
            continue;
        break;
    }

    B=INF;
    A=1;
    dfs(rt,-1);
    dbg(A,B);
    const lli noA=A;
    lli l=0,r=INF;
    while(r-l>1)
    {
        B=(l+r)/2;
        A=1;
        if(dfs(rt,-1)-1>B)
            A=INF;
        dbg(B,A,noA);
        if(A<=noA)
            r=B;
        else
            l=B;
    }
    cout<<noA<<" "<<r<<endl;
}   aryanc403();
    return 0;
}

Submission Info

Submission Time
Task F - Christmas Tree
User aryanc403
Language C++ (GCC 9.2.1)
Score 900
Code Size 4061 Byte
Status AC
Exec Time 1094 ms
Memory 22740 KB

Compile Error

./Main.cpp: In function ‘lli dfs(lli, lli)’:
./Main.cpp:108:17: warning: capture of variable ‘B’ with non-automatic storage duration
  108 |     auto chk=[b,B](const lli m)-> bool {
      |                 ^
./Main.cpp:86:11: note: ‘lli B’ declared here
   86 |     lli A,B;
      |           ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 75
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 840 ms 9256 KB
02.txt AC 905 ms 9220 KB
03.txt AC 848 ms 9228 KB
04.txt AC 819 ms 9208 KB
05.txt AC 832 ms 22696 KB
06.txt AC 927 ms 22740 KB
07.txt AC 1040 ms 12996 KB
08.txt AC 996 ms 15588 KB
09.txt AC 1006 ms 15108 KB
10.txt AC 1011 ms 16148 KB
11.txt AC 1001 ms 10168 KB
12.txt AC 933 ms 10128 KB
13.txt AC 1015 ms 10216 KB
14.txt AC 993 ms 10256 KB
15.txt AC 869 ms 9200 KB
16.txt AC 979 ms 9164 KB
17.txt AC 903 ms 8996 KB
18.txt AC 735 ms 8888 KB
19.txt AC 690 ms 8940 KB
20.txt AC 682 ms 9020 KB
21.txt AC 726 ms 9252 KB
22.txt AC 745 ms 10528 KB
23.txt AC 925 ms 15032 KB
24.txt AC 926 ms 17992 KB
25.txt AC 917 ms 9220 KB
26.txt AC 941 ms 9296 KB
27.txt AC 878 ms 8992 KB
28.txt AC 789 ms 8968 KB
29.txt AC 754 ms 8988 KB
30.txt AC 710 ms 8936 KB
31.txt AC 697 ms 9196 KB
32.txt AC 792 ms 10840 KB
33.txt AC 1005 ms 21076 KB
34.txt AC 1009 ms 20296 KB
35.txt AC 1081 ms 9256 KB
36.txt AC 960 ms 9724 KB
37.txt AC 944 ms 9200 KB
38.txt AC 852 ms 8900 KB
39.txt AC 754 ms 8992 KB
40.txt AC 694 ms 8960 KB
41.txt AC 698 ms 9204 KB
42.txt AC 818 ms 10280 KB
43.txt AC 1001 ms 16880 KB
44.txt AC 942 ms 16328 KB
45.txt AC 864 ms 9196 KB
46.txt AC 884 ms 9252 KB
47.txt AC 875 ms 9232 KB
48.txt AC 802 ms 9036 KB
49.txt AC 730 ms 9036 KB
50.txt AC 696 ms 8940 KB
51.txt AC 667 ms 8896 KB
52.txt AC 712 ms 10124 KB
53.txt AC 876 ms 15540 KB
54.txt AC 947 ms 15368 KB
55.txt AC 1022 ms 11316 KB
56.txt AC 1094 ms 11364 KB
57.txt AC 1049 ms 11316 KB
58.txt AC 1059 ms 11264 KB
59.txt AC 1004 ms 12900 KB
60.txt AC 1040 ms 11920 KB
61.txt AC 990 ms 14268 KB
62.txt AC 1030 ms 12916 KB
63.txt AC 921 ms 13432 KB
64.txt AC 955 ms 16844 KB
65.txt AC 1034 ms 15480 KB
66.txt AC 1035 ms 19088 KB
67.txt AC 2 ms 3608 KB
68.txt AC 2 ms 3544 KB
69.txt AC 2 ms 3648 KB
70.txt AC 2 ms 3492 KB
71.txt AC 5 ms 3564 KB
72.txt AC 2 ms 3612 KB
s1.txt AC 3 ms 3448 KB
s2.txt AC 3 ms 3584 KB
s3.txt AC 2 ms 3600 KB