Submission #19540780


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;
    vector<ii> cc;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

void dfs0(lli u,lli p)
{
    if(sz(e[u])==1)
        return;
    lli cnt=0;
    for(auto x:e[u])
    {
        if(x==p)
            continue;
        dfs0(x,u);
        cnt++;
    }
    A+=cnt/2;
    cnt%=2;
    if(p==-1&&cnt)
        A++;
    return;
}

//len,mx.
ii dfs(lli u,lli p)
{
    if(sz(e[u])==1)
        return {1,0};
    vi b;
    lli mx=0;
    for(auto x:e[u])
    {
        if(x==p)
            continue;
        cc[x]=dfs(x,u);
        dbg("ret",x,cc[x]);
        b.pb(cc[x].X);
        mx=max(mx,cc[x].Y);
    }

    sort(all(b));
    lli i=0,j=sz(b)-1;
    while(i<j)
    {
        mx=max(mx,b[i]+b[j]);
        i++;
        j--;
    }

    if(i==j)
        return {b[i]+1,mx};
    return {1,mx};
}

lli gt(const vi &x,const vi &y)
{
    return max({x[1],y[1],x[0]+y[0]});
}

void dfs2(lli u,lli p,ii pu)
{
    if(u==-1)
        return;
    dbg(u,pu,"ent");
    if(sz(e[u])==1)
    {
        B=min(B,max(pu.Y,pu.X));
        return;
    }

    vector<vi> bb;
    for(auto x:e[u])
    {
        if(x==p)
        {
            if(pu.X)
                bb.pb({pu.X,pu.Y,-1});
            continue;
        }
        bb.pb({cc[x].X,cc[x].Y,x});
    }

    sort(all(bb));

    const lli n=sz(bb);
    lli i=0,j=n-1,cur=0;
    while(i<j)
    {
        cur=max(cur,bb[i][1]);
        cur=max(cur,bb[j][1]);
        cur=max(cur,bb[i][0]+bb[j][0]);
        i++;
        j--;
    }

    if(i==j)
        cur=max({cur,bb[i][0],bb[i][1]});
    B=min(B,cur);
    dbg(u,cur,bb);
    map<lli,lli> mm,pr;
    mm[0]++;
    i=1,j=n-1;
    while(i<j)
    {
        mm[gt(bb[i],bb[j])]++;
        pr[i]=j;pr[j]=i;
        i++;j--;
    }

    for(lli i=0;i<n;++i)
    {
        lli mx=mm.rbegin()->X;
        lli rem=1;
        if(n%2==0)
        {
            lli v=n/2;
            if(i>=n/2)
                v--;
            rem=1+bb[v][0];
            mx=max(mx,bb[v][1]);
        }

        dfs2(bb[i][2],u,{rem,mx});
        if(pr.find(i+1)!=pr.end())
        {
            const lli g=pr[i+1];
            del(mm,gt(bb[i+1],bb[g]));
            pr.erase(g);
            pr.erase(i+1);
            mm[gt(bb[i],bb[g])]++;
            pr[g]=i;
            pr[i]=g;
        }
    }
}



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);
    cc.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;
    }

    dfs0(rt,-1);
    B=INF;
    dfs(rt,-1);
    dfs2(rt,-1,{0,0});
    cout<<A<<" "<<B<<endl;
}   aryanc403();
    return 0;
}

Submission Info

Submission Time
Task F - Christmas Tree
User aryanc403
Language C++ (GCC 9.2.1)
Score 0
Code Size 5258 Byte
Status WA
Exec Time 196 ms
Memory 56708 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 38
WA × 37
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 92 ms 11032 KB
02.txt AC 97 ms 11060 KB
03.txt WA 96 ms 11036 KB
04.txt AC 91 ms 11096 KB
05.txt AC 124 ms 49420 KB
06.txt AC 132 ms 56708 KB
07.txt WA 127 ms 40064 KB
08.txt WA 118 ms 31972 KB
09.txt WA 116 ms 32236 KB
10.txt WA 117 ms 32684 KB
11.txt AC 143 ms 18424 KB
12.txt AC 144 ms 19432 KB
13.txt AC 140 ms 17144 KB
14.txt AC 141 ms 18424 KB
15.txt WA 91 ms 11060 KB
16.txt WA 94 ms 11056 KB
17.txt WA 89 ms 10832 KB
18.txt WA 84 ms 10860 KB
19.txt WA 90 ms 10824 KB
20.txt WA 97 ms 11048 KB
21.txt WA 89 ms 11876 KB
22.txt WA 97 ms 15584 KB
23.txt AC 129 ms 49140 KB
24.txt AC 122 ms 45940 KB
25.txt WA 96 ms 11064 KB
26.txt WA 97 ms 11036 KB
27.txt WA 96 ms 10824 KB
28.txt WA 88 ms 10564 KB
29.txt WA 85 ms 10832 KB
30.txt WA 82 ms 11016 KB
31.txt WA 90 ms 12336 KB
32.txt WA 96 ms 16640 KB
33.txt AC 127 ms 48076 KB
34.txt AC 119 ms 41940 KB
35.txt AC 90 ms 11056 KB
36.txt AC 97 ms 11292 KB
37.txt WA 91 ms 11032 KB
38.txt WA 95 ms 10772 KB
39.txt WA 87 ms 10792 KB
40.txt WA 82 ms 11128 KB
41.txt WA 84 ms 11836 KB
42.txt WA 98 ms 17372 KB
43.txt WA 114 ms 32248 KB
44.txt WA 111 ms 31200 KB
45.txt WA 93 ms 11028 KB
46.txt AC 97 ms 11040 KB
47.txt WA 97 ms 11032 KB
48.txt WA 89 ms 10876 KB
49.txt WA 88 ms 10764 KB
50.txt WA 84 ms 11380 KB
51.txt WA 88 ms 12112 KB
52.txt WA 97 ms 14456 KB
53.txt AC 113 ms 26604 KB
54.txt AC 120 ms 39012 KB
55.txt AC 194 ms 22716 KB
56.txt AC 194 ms 22620 KB
57.txt AC 193 ms 22680 KB
58.txt AC 196 ms 22680 KB
59.txt AC 102 ms 30368 KB
60.txt AC 100 ms 25840 KB
61.txt AC 100 ms 27692 KB
62.txt AC 96 ms 25284 KB
63.txt AC 100 ms 28252 KB
64.txt AC 149 ms 39008 KB
65.txt AC 167 ms 27172 KB
66.txt AC 135 ms 32172 KB
67.txt AC 2 ms 3488 KB
68.txt AC 4 ms 3540 KB
69.txt AC 2 ms 3560 KB
70.txt AC 2 ms 3524 KB
71.txt AC 3 ms 3488 KB
72.txt AC 2 ms 3548 KB
s1.txt AC 3 ms 3496 KB
s2.txt AC 2 ms 3536 KB
s3.txt AC 3 ms 3536 KB