oj.uz

Submission #563381

# Submission time Handle Problem Language Result Execution time Memory
563381 2022-05-17T04:04:34 Z gg123_pe Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 86 ms 10004 KB 
#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];
    }
    cout << ans << "\n";
    return 0; 
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 10004 KB Output isn't correct
2 Halted 0 ms 0 KB -