Submission #563740

#	Time	Username	Problem	Language	Result	Execution time	Memory
563740		gg123_pe	Shymbulak (IZhO14_shymbulak)	C++14	100 / 100	281 ms	34952 KiB

shymbulak

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<ll,ll> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define ff first 
#define ss second 

const int N = 2e5 + 5; 
const ll inf = 1e17 + 100; 


ll ans, a[N], c[N], diam; 
ii val[N], ra[N]; 

int n, ct, H, pu, pv; 
int h[N], p[N]; 
bool vis[N], revis[N], on[N]; 
vector <int> adj[N], cycle; 
vector <ii> ADJ[N]; 

void dfs(int u, int f){
    vis[u] = 1; 
    p[u] = f; 

    for(int v: adj[u]){
        if(v == f) continue; 
        if(vis[v])
            {if(pv == 0) pv = v, pu = u; }
        else dfs(v, u); 
    }
}

void cal(int u){
    revis[u] = 1; 
    H = max(H, h[u]); 

    ii p = {0, 0}, ct; 

    for(int v: adj[u]){
        if(revis[v]) continue; 
        h[v] = h[u] + 1; 
        cal(v); 

        
        map <ll,ll> m; 
        for(auto p: ADJ[v]) m[-p.ff] += p.ss;  
        ll wi = 0, ta = 0; 
        for(auto p: m){
            wi = -p.ff, ta = p.ss; 
            break; 
        }
        ADJ[u].push_back({++wi, ta});

        if(val[v].ff + 1 > p.ff) { 
            p.ss = p.ff, p.ff = val[v].ff + 1;
            ct = val[v];
            ct.ff++;  
        }
        else {
            if(val[v].ff + 1 == p.ff) ct.ss++; 
            if(val[v].ff + 1 > p.ss) p.ss = val[v].ff + 1;
        }  
    }

    val[u] = ct; 
    ra[u].ff = p.ff, ra[u].ss = p.ss; 

    if(ADJ[u].empty()) ADJ[u].push_back({0, 1}); 
    //cout << u << "\n"; 
    //for(auto p: ADJ[u]) cout << p.ff << " " << p.ss << "\n"; 
    diam = max(diam, p.ff + p.ss); 
}

void get(int u){
    on[u] = 1; 
    if(h[u] == H) ct++;

    for(int v: adj[u]){
        if(!on[v]) get(v);
    }
}

void DFS(int u){
    on[u] = 1; 
    
    if(ra[u].ff + ra[u].ss == diam){
        int l = ADJ[u].size(); 
        if(l) {
            sort(ADJ[u].begin(), ADJ[u].end()); 
            reverse(ADJ[u].begin(), ADJ[u].end()); 
        }

        if(l == 1) ans += ADJ[u][0].ss; 
        else{
    
            ll s = 0, s_2 = 0; 
            //for(auto p: ADJ[u]){
            //    cout << p.ff << " " << p.ss << "\n"; 
            //}
            f(i,0,2) s += ADJ[u][i].ss, s_2 += ADJ[u][i].ss * ADJ[u][i].ss; 
            f(i,2,l){
                if(ADJ[u][i].ff != ADJ[u][1].ff) break; 
                s_2 += ADJ[u][i].ss * ADJ[u][i].ss; 
                s += ADJ[u][i].ss; 
            }
            if(ADJ[u][0].ff == ADJ[u][1].ff){
                ans += (s*s - s_2) / 2; 
            }
            else{
                ans += ADJ[u][0].ss * (s - ADJ[u][0].ss); 
            }
        }
    }
    for(int v: adj[u]) if(!on[v]) DFS(v);
}
int main(){
    cin >> n; 

    f(i,0,n){
        int x, y; cin >> x >> y; 
        adj[x].push_back(y), adj[y].push_back(x); 
    }

    dfs(1, 0); 

    while(pu != p[pv]) cycle.push_back(pu), pu = p[pu];
    for(int x: cycle) revis[x] = on[x] = 1;

    int id = 0; 

    for(int x: cycle){
        H = 0, ct = 0; 
        id++; 

        cal(x), get(x); 
        a[id] = H, c[id] = ct; 
    }

    ll x = id/2; 
    map <int,ll> ml, mr; 
    multiset <int> sl, sr; 

    f(i,1,id+1){
        if(!sr.empty())
            diam = max(diam, i + a[i] + *sr.rbegin());

        if(!sl.empty())
            diam = max(diam, id - i + a[i] + *sl.rbegin()); 

        sr.insert(a[i] - i);
        if(i >= x + 1){
            sl.insert(a[i-x] + i-x); 
            auto it = sr.find(a[i-x] - (i-x));
            sr.erase(it); 
        }
    }

    f(i,1,id+1){
        ans += c[i] * (mr[diam - a[i] - i] + ml[diam - id - a[i] + i]);

        mr[a[i] - i] += c[i]; 
        if(i >= x + 1){
            ml[a[i-x] + i - x] += c[i-x]; 
            mr[a[i-x] - i + x] -= c[i-x]; 
        }

        if(2*x == id and i >= x+1 and a[i] + x + a[i-x] == diam)
            ans += c[i] * c[i-x];
    }
    
    f(i,1,n+1) on[i] = 0; 
    for(int x: cycle) on[x] = 1;

    for(int x: cycle)
        DFS(x); 
    
    cout << ans << "\n";
    return 0; 
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50