Submission #1182113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182113		fadak-14	Hard route (IZhO17_road)	C++20	100 / 100	406 ms	152592 KiB

road

//Wa of course, please give me ac !!! im begging u compiler-sama, have mercy on my poor code !
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define endl '\n'
#define eb emplace_back
#define em emplace
#define pb push_back
#define pf push_front
#define pp pop_back
#define fr first
#define sc second
#define sz size
/*vector<bool> f(26 , true) ;
bool va[mn][mn] = {false};
bool vb[mn][mn] = {false};
ll dp[mn][mn];*/
/*
const ll mn = 1771;
ll lch[mn], rch[mn];
vector<ll> ed[mn];
deque<ll> rs[mn];
set<ll> v[mn];
bool us[mn];
pair<ll, ll> ar[mn];
ll prv[mn], rnk[mn];
bool lf[mn];
bool va[mn][mn] = {false};
bool vb[mn][mn] = {false};*/
/*
const ll mn = 5e5+10 ;
const ll mod = 1e9+7;
ll a[mn], fa[mn];
vector<tuple<ll, ll, ll>> ed; 
ll find(ll x) {
    return (x == fa[x])? x:(fa[x] = find(fa[x]));
}*/
//ll b[400014];
/*
string a[]= {"01" , "1" , "23456789", "0123456789"} ;
const ll mxn = 1e5 + 14 ;
const ll dx[] = {-1 , 0 , 1 , 0} ;
const ll dy[] = {0 , 1 , 0 , -1} ;
vector <ll> adj[mxn] ;
ll p[mxn][2] ;
*/
/*
ll bit(ll n){
    for(ll i = 0 ; i < 32 ; i++) {if((! (n& (1 << i))) and n &(1 << ( i + 1))) return(i);}
}
*/
//ll n ,m ;
vector<vector<ll>> dp ;
const ll mx = 500014;
vector<ll> g[mx] ;
ll up[mx] ;
ll dn [mx];
ll uf[mx] ;
ll df[mx] ;
ll mxi= 0 ;
ll cnt = 1 ;
ll eds(ll i1, ll j1, ll i2, ll j2) {
    return (ll)(i1 - i2) * (i1 - i2) + (ll)(j1 - j2) * (j1 - j2);
}
db dou(db x) {return x * x ;} 
vector<ll> cps(const vector<ll> & arr , ll n) {
    vector <ll> ps(n + 1 , 0) ;
    for(ll i =0 ; i <n ; i++) ps[i + 1] = ps[i] + arr[i] ;
    return ps ;
} 
/*
const ll mx = 200014;
ll d[mx] ; ll e[mx];
vector<ll> a[mx];
vector <ll> aa[mx];
const ll md = 998244353;
ll n , k , u , v ;
*/

/*
ll cvp(ll n , ll k ,ll x , const vector<ll> & arr){
    vector <ll> ps = cps(arr , n) ;
    ll ts = ps[n] ;
    ll count = 0 ;
    for(ll s = 0 ; s < n ; s++) {
        ll sm = 0 ;
        for(ll c = 0 ; c < k ; c++) {
            for(ll i = s; i < n ; i++) {
                sm += arr[i] ;
                if(sm >= x) {
                    count ++ ;
                    break ;
                }
            }
        }
    }
    return count ;
}*/
void upd(ll x ,ll f) {
    if(x > mxi) mxi = x , cnt = f ;
    else if(x == mxi) cnt += f ;
}
ll nx(string s){
	cout << "next" ;
    cout.flush();
    for(auto i: s) cout << " " << i ;
    cout << endl ;
    cout.flush() ;
    ll n ; cin >> n ;
    for(ll i = 1 ; i <= n ;i++) cin >> s ;
    return n ;
}
bool ip(const string& s) {
    if(s == "1") return false ;
    if(s.length() <= 18) {
        ll nm = stoll(s) ;
        if(nm < 2) return false ;
        for(ll i = 2; i * i <= nm ;i++) if(nm % i == 0) return false ;
        return true;
    }
    vector<ll> prm = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
                          53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
                          109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
                          173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
                          233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
                          293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
                          367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
                          433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
                          499, 503, 509, 521, 523, 541};
    for(ll i : prm){
        ll rm = 0 ;
        for(char c:s) rm = (rm *10 + (c - '0')) % i ;
        if(rm == 0) return false ;
    }
    return true;
}
/*
double cc(const string& num) {
    ll sod = 0;
    for (char i : num) sod += i - '0';
    double vl = 0;
    for (char i : num) vl = vl * 10 + (i - '0');
    double c = vl / sod;
    return c;
}
*/
/*
ll mmdtv(const string& n) {
    ll len = n.size() ;
    ll mnr = len - 1;
    double mc = 1e18;
    for(ll m = 1 ; m < (1 << len) ; m++) {
        string r ;
        for(ll i = 0 ; i < len ; i++) if(m & (1 << i)) r += n[i] ;
        if(!r.empty()) {
            double c = cc(r) ;
            ll rv = len - r.size();
            if(c < mc || (abs(c - mc) < 1e-9 && rv < mnr)) {mc = c;mnr = rv; }
        }
    }
    return mnr;
}
*/
/*
bool sv(ll c , ll i , vector <ll> &arr, vector<vector<ll>> &sm) {
    if(i == n) return true ;
    if(dp[c][i] != -1) return dp[c][i] ;
    for(ll &j : sm[arr[i]]) {
        if(j & c) continue ;
        if(sv(j | c , i +1 , arr , sm)){ return dp[c][i] = 1 ; return true;}
    }
    dp[c][i] = 0 ;
    return false ;
}
*/
ll gp(ll lv, ll rw, ll cl) {
    if (lv == 1) {
        if (rw == 1 && cl == 1) return 1;
        if (rw == 2 && cl == 2) return 2;
        if (rw == 2 && cl == 1) return 3;
        return 4; 
    }
    ll hf = 1 << (lv - 1);
    ll bc = 1LL << (2 * (lv - 1));
    if (rw <= hf && cl <= hf)return gp(lv - 1, rw, cl);
    if (rw > hf && cl > hf)return bc + gp(lv - 1, rw - hf, cl - hf);
    if (rw > hf && cl <= hf)return 2 * bc + gp(lv - 1, rw - hf, cl);
    return 3 * bc + gp(lv - 1, rw, cl - hf);
}
pair<ll , ll> getp(ll lv, ll ps) {
    if (lv == 1) {
        if (ps == 1) return {1, 1};
        if (ps == 2) return {2, 2};
        if (ps == 3) return {2, 1};
        return {1, 2};
    }
    ll hf = 1 << (lv - 1);
    ll bs = 1LL << (2 * (lv - 1));
    if (ps <= bs)return getp(lv - 1, ps);
    if (ps <= 2 * bs) {auto p = getp(lv - 1, ps - bs);return {p.fr + hf, p.sc + hf};}
    if (ps <= 3 * bs) { auto p = getp(lv - 1, ps - 2 * bs);return {p.fr + hf, p.sc}; }
    auto p = getp(lv - 1, ps - 3 * bs);
    return {p.fr, p.sc + hf};
}
bool prime(ll n) {
    if(n < 2) return false ;
    for(ll i =2; i*i <= n ; i++) if(n % i == 0) return false ;
    return true ;
}
void dfs(ll u , ll p) {
    uf[u] =  df[u] = 1 ;
    for(ll v : g[u]) {
        if(v== p) continue ;
        dfs(v, u) ;
        if(dn[u] < dn[v] + 1) dn[u] = dn[v] + 1 , df[u] = df[v] ;
        else if(dn[u] == dn[v] + 1) df[u] += df[v] ;
    }
}
void dfs1 (ll u, ll p) {
    vector<array <ll , 2>> v ;
    v.pb({up[u] , uf[u]}) ;
    for(ll x : g[u]) if(x != p) v.pb({dn[x] + 1 , df[x]}) ;
    sort(v.rbegin() , v.rend()) ;
    if(g[u].sz() > 2) {
        ll a =v[0][0] , b = v[1][0] ,c = v[2][0] ;
        ll val = a* (b +c) ;
        if(a != b && b != c) {
            ll s= 0 ;
            for(auto [l ,f] : v)if(l == c) s += f ;
            upd(val, v[1][1] * s) ;
        }
        else if(a == b && b == c){
            ll s = 0 ;
            ll r = 0;
            for(auto [l ,f] : v) if(l == c) s+= f;
            for(auto [l , f] : v) if(l == c) r += f*(s - f) ;
            upd(val , r/2) ;
        }
        else if(a == b) {
            ll s = 0 ;
            for(auto [l ,f] : v) if(l == c) s += f;
            upd(val , (v[0][1] + v[1][1]) * s) ;
        }
        else if(b == c){
            ll s= 0 , r = 0 ;
            for(auto [l ,f] : v) {
                if(l == c) s += f;
            }
            for(auto[l ,f] : v) if(l == c) r += f*(s - f);
            upd(val , r /2) ;
        }
    }
    ll a1  = 0, a2 = 0 ;
    for(auto [l , f] : v) if(l == v[0][0]) a1 += f;
    for(auto [l , f] : v) if(l == v[1][0]) a2 += f;
    for(ll x : g[u]){
        if(x == p) continue ;
        ll len = dn[x] + 1;
        if(len == v[0][0]) {
            a1 -= df[x] ;
            if (a1 == 0)up[x] = v[1][0] + 1, uf[x] = a2;
            else up[x] = v[0][0] + 1, uf[x] = a1;
        }
        else up[x] = v[0][0] + 1 , uf[x] = a1 ;
        dfs1(x , u);
    } 
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) ; cout.tie(0);
    /*ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++)cin >> a[i];
    if (k == 1) {
        ll tt = 0;
        for (ll nm : a) tt += nm;
        cout << tt << endl;
        return 0;
    }
    ll lm = n -k + 1;
    vector<ll> pr(n + 1, 0);
    for (ll i = 0; i < n; i++) pr[i + 1] = pr[i] + a[i];
    deque<ll> dq; 
    ll ms = 1e18;
    for (ll i = 0; i < n; i++) {
        ll cs = max(0LL, i - lm + 1);
        while (!dq.empty() && dq.front() < cs) dq.pop_front();
        while (!dq.empty() && pr[i] >= pr[dq.back()])dq.pp();
        dq.pb(i);
        ll cmp = pr[dq.front()];
        ll css = pr[i + 1] - cmp;
        if (css < ms) ms = css;
    }
    cout << ms << endl;*/
    ll n;
    cin >> n; n-- ;
    while(n--) {
        ll u , v ;
        cin >> u >> v ;
        g[u].pb(v) ; g[v].pb(u) ;
    }
    dfs(1 , 0) ;
    dfs1(1 , 0) ;
    cout << mxi << " " << cnt ;    
    //char s[200014] ;
    /*ll t;
    cin >>t ;
    while(t--) {
        ll n ; cin >> n ;
    }
    */
    /*while(true){ll ans = nx(a[0]) ; ans = nx(a[1]) ; if(ans == 2) break;}
    while(true) {ll ans = nx(a[3]) ;if(ans == 1) break ;}
    cout << "done" << endl ; 
    cout.flush() ;*/
    //ll t; cin >> t ;
    //while(t--){
        /*ll n ;
        cin >> n ;
        ll q ;
        cin >> q ;
        while(q--) {
            string s;
            cin >> s ;
            if(s == "->") {ll x ,y ; cin >> x >>y ; cout << gp(n , x ,y) << endl ;}
            else {ll d ; cin >> d ; pair<ll , ll> p = getp(n , d) ; cout << p.fr << " " << p.sc << endl;}
        }*/
        /*string n ; cin >> n ;
        //cout << mmdtv(n) << endl ;
        //i'll try another bad idea
        //ok
        ll mx = 0 ;
        ll count = 0 ;
        for(auto i : n) {
            if(i == '0') count ++ ;
            else mx = max(mx, count + 1) ;
        }
        cout << n.sz() - mx << endl;*/
    return 0 ;
}
  

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48