Submission #37452

#	Time	Username	Problem	Language	Result	Execution time	Memory
37452		nickyrio	Shymbulak (IZhO14_shymbulak)	C++14	100 / 100	159 ms	60728 KiB

shymbulak

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define taskname "Test"
using namespace std;
typedef long long Counter;
typedef int Depth;
typedef pair<Depth, Counter> DC;
int n, visited[N], inCycle[N];
vector<int> e[N], Cycle;
int maxLength;
long long cnt;
stack<int> st;
int depth[N];
DC f[N];
bool Find_Cycle(int u, int p) {
    if (visited[u]) {
        while (true) {
            int v = st.top();
            inCycle[v] = 1;
            st.pop();
            Cycle.push_back(v);
            if (u == v) return true;
        }
    }
    st.push(u);
    visited[u] = 1;
    for (int v : e[u]) if (v != p) {
        if (Find_Cycle(v, u)) return true;
    }
    visited[u] = 0;
    st.pop();
    return false;
}

void Update(DC best, DC now) {
    if (now.first + best.first == maxLength) {
        cnt += now.second * best.second;
    }
    else {
        if (now.first + best.first > maxLength) {
            maxLength = now.first + best.first;
            cnt = now.second * best.second;
        }
    }
}

DC FindMaxDepth(int u, int p) {
    // Find maxLength in each Tree with root is a vertex in cycle
    DC best = make_pair(1, 1);
    for (int v : e[u]) if (v != p && !inCycle[v]) {
        depth[v] = depth[u] + 1;
        DC now = FindMaxDepth(v, u);
        Update(best, now);
        now.first++;
        if (best.first == now.first) best.second += now.second;
        else {
            if (best.first < now.first) best = now;
        }
    }
    Update(best, DC(0, 1));
    return best;
}
map<Depth, Counter> tab;
void FindInCycle() {
    int nCycle = Cycle.size();
    int sz = nCycle / 2;
    REP(i, sz) Cycle.push_back(Cycle[i]);
    tab.insert(f[Cycle[0]]);
    FOR(i, 1, nCycle + sz - 1) {
        DC best = *tab.rbegin();
        DC now = f[Cycle[i]]; now.first += i - 1;
        Update(best, now);
        //cout << i << ':' << maxLength << ' ' << cnt << endl;
        if (i < nCycle) {
            now.first -= 2 * i - 1;
            tab[now.first] += now.second;
        }
        if (i >= sz) {
            tab[f[Cycle[i - sz]].first - (i - sz)] -= f[Cycle[i - sz]].second;
            if (tab[f[Cycle[i - sz]].first - (i - sz)] == 0) {
                tab.erase(f[Cycle[i - sz]].first - (i - sz));
            }
        }
    }
}

int main() {
//    freopen(taskname".inp","r",stdin);
//    freopen(taskname".out","w",stdout);
    IO;
    cin >> n;
    FOR(i, 1, n) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    Find_Cycle(1, -1);
    maxLength = 0;
    cnt = 0;
    for (int u : Cycle) {
        f[u] = FindMaxDepth(u, -1);
        //cout << f[u].first << ' ' << f[u].second << endl;
    }
    FindInCycle();
    cout << cnt;return 0;
}

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