oj.uz

Submission #563740

# Submission time Handle Problem Language Result Execution time Memory
563740 2022-05-18T05:01:02 Z gg123_pe Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 281 ms 34952 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 5 ms 9688 KB Output is correct
4 Correct 5 ms 9748 KB Output is correct
5 Correct 6 ms 9756 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9744 KB Output is correct
14 Correct 6 ms 9804 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9940 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 7 ms 9940 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 9 ms 10196 KB Output is correct
6 Correct 9 ms 10324 KB Output is correct
7 Correct 10 ms 10196 KB Output is correct
8 Correct 9 ms 10324 KB Output is correct
9 Correct 9 ms 10324 KB Output is correct
10 Correct 10 ms 10288 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 20416 KB Output is correct
2 Correct 129 ms 22092 KB Output is correct
3 Correct 126 ms 31952 KB Output is correct
4 Correct 100 ms 21184 KB Output is correct
5 Correct 107 ms 21312 KB Output is correct
6 Correct 281 ms 29996 KB Output is correct
7 Correct 188 ms 26904 KB Output is correct
8 Correct 193 ms 32608 KB Output is correct
9 Correct 226 ms 32800 KB Output is correct
10 Correct 186 ms 34952 KB Output is correct
11 Correct 213 ms 33380 KB Output is correct
12 Correct 220 ms 34560 KB Output is correct