Submission #445753

#	Time	Username	Problem	Language	Result	Execution time	Memory
445753		nickyrio	Shymbulak (IZhO14_shymbulak)	C++17	100 / 100	117 ms	19300 KiB

shymbulak

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 100;

struct Farthest{
    int length;
    long long ways;

    Farthest():length(0), ways(1) {}
    Farthest(int length, long long ways):length(length), ways(ways) {}

    Farthest& operator+= (const Farthest &that) {
        // Combine
        this->length += that.length;
        this->ways *= that.ways;
        return *this;
    }

    Farthest operator+(Farthest that) {
        that += *this;
        return that;
    }

    Farthest& operator*= (const Farthest &that) {
        // Get max
        if (this->length == that.length) this->ways += that.ways;
        if (this->length < that.length) *this = that;
        return *this;
    }

    bool operator<(const Farthest &that) const {
        return this->length < that.length;
    }

}farthest[N];
std::ostream& operator<<(std::ostream& os, const Farthest& f) {
    return os << "Length: " << f.length << ", Ways: " << f.ways << '\n'; 
}

stack<int> st;
vector<int> cycle;
int vis[N], in_cycle[N];
vector<int> e[N];

bool findCycle(int u, int p) {
    st.push(u);
    vis[u] = 1;
    for (int v : e[u]) if (v != p) {
        if (vis[v]) {
            do {
                u = st.top(); st.pop();
                cycle.push_back(u);
                in_cycle[u] = 1;
            } while (v != u);
            return 1;
        } else {
            if (findCycle(v, u)) return true;
        }
    }
    vis[u] = 0;
    st.pop();
    return 0;
}

Farthest findFarthest(int u, int p, int h, Farthest &best) {
    Farthest cur = Farthest(h, 1);
    for (int v : e[u]) if (v != p && !in_cycle[v]) {
        Farthest now = findFarthest(v, u, h + 1, best);
        Farthest combine = cur + now; combine.length -= h * 2;
        best *= combine;
        cur *= now;
    }
    return cur;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    findCycle(1, -1);
    Farthest best;
    for (int u : cycle) {
        farthest[u] = findFarthest(u, -1, 0, best);
    } 
    n = cycle.size();
    int half = cycle.size() / 2;
    map<int, int> branches;
    for (int i = 0; i < n + half; ++i) {
        // Query 
        Farthest curr = farthest[cycle[i % n]];
        int length = curr.length;
        if (i) {
            int _farthest = branches.rbegin() -> first;
            best *= curr + Farthest(_farthest + i, branches[_farthest]);           
        }
        // Update 
        if (i < cycle.size()) {
            branches[curr.length - i] += curr.ways;
        }
        // remove front, keep only a half of cycle. 
        // pop farthest[i - half]
        if (i >= half) {
            Farthest half_prev = farthest[cycle[i - half]];
            branches[half_prev.length - (i - half)] -= half_prev.ways;
            if (branches[half_prev.length - (i - half)] == 0) {
                branches.erase(half_prev.length - (i - half));
            }
        }
    }
    cout << best.ways << '\n';
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:104:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         if (i < cycle.size()) {
      |             ~~^~~~~~~~~~~~~~
shymbulak.cpp:98:13: warning: unused variable 'length' [-Wunused-variable]
   98 |         int length = curr.length;
      |             ^~~~~~

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