Submission #1276460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276460		HasanV11010238	Shymbulak (IZhO14_shymbulak)	C++20	100 / 100	128 ms	17464 KiB

shymbulak

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000000000000
#define mod 9929
using namespace std;
vector<vector<int>> v;
vector<int> ord, bl, al, vis;
bool f = 0;
void dfs(int x, int p){
    vis[x] = 1;
    ord.push_back(x);
    for (auto el : v[x]){
        if (vis[el] == 0){
            dfs(el, x);
        }
        else if (vis[el] == 1 && el != p && f == 0){
            int cur = (int)ord.size() - 1;
            f = 1;
            while (ord[cur] != el){
                al.push_back(ord[cur]);
                cur--;
            }
            al.push_back(el);
        }
    }
    ord.pop_back();
}
ll de = 0, cnt = 0;
vector<ll> dd, cn;
void dfs2(int x, int p){
    dd[x] = dd[p] + 1;
    if (dd[x] > de) cnt = 0, de = dd[x];
    if (dd[x] == de) cnt += 1;
    ll d1 = dd[x], ch = 0;
    for (auto el : v[x]){
        if (el != p && bl[el] == 0){
            ch++;
            dfs2(el, x);
            if (d1 + dd[el] - 2 * dd[x] > de) cnt = 0, de = d1 + dd[el] - 2 * dd[x];
            if (d1 + dd[el] - 2 * dd[x] == de) cnt += cn[x] * cn[el];
 
            if (dd[el] > d1) cn[x] = 0, d1 = dd[el];
            if (dd[el] == d1) cn[x] += cn[el];
        }
    }
    if (ch == 0) cn[x] = 1;
    dd[x] = d1;
}
 
int main(){
    int n, a, b;
    cin>>n;
    v.assign(n + 1, vector<int>()), vis.assign(n + 1, 0), bl.assign(n + 1, 0), dd.assign(n + 1, 0), cn.assign(n + 1, 0);
    for (int i = 0; i < n; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dd[0] = -1;
    dfs(1, 0);
    if (al.size() <= 2) assert(false);
    for (auto el : al){
        bl[el] = 1;
    }
    for (auto el : al){
        dfs2(el, 0);
    }
    int k = al.size();
    for (int i = 0; i < k; i++) al.push_back(al[i]);
    map<ll, ll, greater<ll>> ma;
    ll si = k / 2;
    for (int i = k - si; i < k; i++){
        ma[dd[al[i]] - i] += cn[al[i]];
    }
    for (ll i = k; i < 2 * k; i++){
        while (1){
            if (ma.begin()->second != 0) break;
            ma.erase(ma.begin());
        }
        ll ss = dd[al[i]] + ma.begin()->first + i;
        if (ss > de) cnt = 0, de = ss;
        if (ss == de) cnt += ma.begin()->second * cn[al[i]];
        ma[dd[al[i]] - i] += cn[al[i]];
        ll oth = i - si;
        ma[dd[al[oth]] - oth] -= cn[al[oth]];
    }
    cout<<cnt;
}

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