oj.uz

Submission #445753

# Submission time Handle Problem Language Result Execution time Memory
445753 2021-07-19T13:35:10 Z nickyrio Shymbulak (IZhO14_shymbulak) C++17
100 / 100
 117 ms 19300 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 4 ms 8140 KB Output is correct
6 Correct 4 ms 8140 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 4 ms 8140 KB Output is correct
9 Correct 4 ms 8152 KB Output is correct
10 Correct 4 ms 8140 KB Output is correct
11 Correct 4 ms 8140 KB Output is correct
12 Correct 4 ms 8140 KB Output is correct
13 Correct 4 ms 8152 KB Output is correct
14 Correct 5 ms 8152 KB Output is correct
15 Correct 5 ms 8140 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8152 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 6 ms 8396 KB Output is correct
6 Correct 7 ms 8396 KB Output is correct
7 Correct 6 ms 8288 KB Output is correct
8 Correct 6 ms 8292 KB Output is correct
9 Correct 6 ms 8396 KB Output is correct
10 Correct 7 ms 8268 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12504 KB Output is correct
2 Correct 49 ms 13016 KB Output is correct
3 Correct 50 ms 17292 KB Output is correct
4 Correct 39 ms 13200 KB Output is correct
5 Correct 47 ms 13280 KB Output is correct
6 Correct 117 ms 16708 KB Output is correct
7 Correct 103 ms 15060 KB Output is correct
8 Correct 76 ms 18244 KB Output is correct
9 Correct 79 ms 17912 KB Output is correct
10 Correct 74 ms 19300 KB Output is correct
11 Correct 79 ms 17808 KB Output is correct
12 Correct 80 ms 18360 KB Output is correct