Submission #19540812


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)
{
    if(sz(e[u])==1)
        return 1;
    map<lli,lli> bb;
    lli cnt=0;
    for(auto x:e[u])
    {
        if(x==p)
            continue;
        bb[dfs(x,u)]++;
        cnt++;
    }

    dbg(bb,cnt,B);
    while(cnt>1)
    {
        auto mx=bb.rbegin()->X;
        del(bb,mx);
        cnt--;
        A++;
        auto it=bb.upper_bound(B-mx);
        dbg(mx,B-mx,bb,cnt);
        if(it==bb.begin())
            continue;
        dbg(mx,it->X,"Hello");
        --it;
        del(bb,it->X);
        cnt--;
    }

    if(p==-1&&cnt)
        A++;
    if(cnt==0)
        return 1;
    if(cnt&&bb.begin()->X==B)
    {
        A++;
        return 1;
    }
    return bb.begin()->X+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;
    dfs(rt,-1);
    dbg(A,B);
    const lli noA=A;
    lli l=0,r=INF;
    while(r-l>1)
    {
        B=(l+r)/2;
        A=0;
        dfs(rt,-1);
        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 0
Code Size 3845 Byte
Status WA
Exec Time 53 ms
Memory 9752 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
WA × 3
AC × 1
WA × 74
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 WA 46 ms 9292 KB
02.txt WA 45 ms 9280 KB
03.txt WA 46 ms 9208 KB
04.txt WA 45 ms 9168 KB
05.txt WA 44 ms 8748 KB
06.txt WA 44 ms 8720 KB
07.txt WA 48 ms 9232 KB
08.txt WA 49 ms 9228 KB
09.txt WA 52 ms 9224 KB
10.txt WA 48 ms 9228 KB
11.txt WA 43 ms 9660 KB
12.txt WA 45 ms 9628 KB
13.txt WA 41 ms 9724 KB
14.txt WA 42 ms 9668 KB
15.txt WA 45 ms 9276 KB
16.txt WA 43 ms 9168 KB
17.txt WA 45 ms 8900 KB
18.txt WA 44 ms 8732 KB
19.txt WA 43 ms 8680 KB
20.txt WA 47 ms 8704 KB
21.txt WA 42 ms 8732 KB
22.txt WA 49 ms 8640 KB
23.txt WA 50 ms 8676 KB
24.txt WA 47 ms 8676 KB
25.txt WA 46 ms 9276 KB
26.txt WA 47 ms 9216 KB
27.txt WA 42 ms 8948 KB
28.txt WA 46 ms 8680 KB
29.txt WA 47 ms 8680 KB
30.txt WA 48 ms 8732 KB
31.txt WA 47 ms 8772 KB
32.txt WA 49 ms 8672 KB
33.txt WA 48 ms 8780 KB
34.txt WA 47 ms 8688 KB
35.txt WA 44 ms 9228 KB
36.txt WA 47 ms 9752 KB
37.txt WA 39 ms 9232 KB
38.txt WA 47 ms 8960 KB
39.txt WA 48 ms 8732 KB
40.txt WA 48 ms 8680 KB
41.txt WA 45 ms 8704 KB
42.txt WA 48 ms 8696 KB
43.txt WA 46 ms 8704 KB
44.txt WA 53 ms 8788 KB
45.txt WA 51 ms 9276 KB
46.txt WA 47 ms 9316 KB
47.txt WA 50 ms 9260 KB
48.txt WA 49 ms 8964 KB
49.txt WA 45 ms 8684 KB
50.txt WA 45 ms 8704 KB
51.txt WA 43 ms 8732 KB
52.txt WA 47 ms 8668 KB
53.txt WA 47 ms 8700 KB
54.txt WA 46 ms 8684 KB
55.txt WA 35 ms 9528 KB
56.txt WA 37 ms 9532 KB
57.txt WA 40 ms 9528 KB
58.txt WA 39 ms 9588 KB
59.txt WA 43 ms 9212 KB
60.txt WA 48 ms 9204 KB
61.txt WA 45 ms 9232 KB
62.txt WA 50 ms 9280 KB
63.txt WA 52 ms 9224 KB
64.txt WA 45 ms 9160 KB
65.txt WA 45 ms 9668 KB
66.txt WA 46 ms 9160 KB
67.txt AC 3 ms 3608 KB
68.txt WA 2 ms 3452 KB
69.txt WA 2 ms 3612 KB
70.txt WA 3 ms 3544 KB
71.txt WA 2 ms 3504 KB
72.txt WA 2 ms 3528 KB
s1.txt WA 3 ms 3504 KB
s2.txt WA 2 ms 3600 KB
s3.txt WA 2 ms 3512 KB