Submission #563689

#	Time	Username	Problem	Language	Result	Execution time	Memory
563689		gg123_pe	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	84 ms	10024 KiB

shymbulak

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

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)

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


ll ans, a[N], c[N]; 
int n, ct, H, pu, pv; 
int h[N], p[N]; 
bool vis[N], revis[N], on[N]; 
vector <int> adj[N], cycle; 


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]); 

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

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

    for(int v: adj[u]){
        if(!on[v]) get(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; 
    }

    /*
    map <int,ll> ml, mr; 
    multiset <int> sl, sr; 

    ll x = id/2, diam = 0; 

    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];
    }
    */

    ll diam = 0; 

    f(i,1,id+1){
        f(j,i+1,id+1){
            diam = max(diam, a[i] + a[j] + min(j-i, id-j+i)); 
        }
    }

    f(i,1,id+1){
        f(j,i+1,id+1){
            if(a[i] + a[j] + min(j-i, id-j+i) == diam){
                ans += c[i] * c[j]; 
                if(2*min(j-i, id-j+i) == id) ans += c[i] * c[j]; 
            }
        }
    }
    cout << ans << "\n";
    return 0; 
}

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