Submission #447114

#	Time	Username	Problem	Language	Result	Execution time	Memory
447114		nickyrio	Hard route (IZhO17_road)	C++17	0 / 100	27 ms	51268 KiB

road

#include <bits/stdc++.h>

using namespace std;

struct MaxCount {
    int length;
    long long ways;

    MaxCount(): length(0), ways(0) {}
    MaxCount(int length, long long ways):length(length), ways(ways) {} 
    MaxCount(pair<int, long long> it): length(it.first), ways(it.second) {} 
    
    bool operator<(const MaxCount& that) const { return this -> length < that.length; }
    void merge(const MaxCount& that) {
        if (this -> length == that.length) {
            this->ways += that.ways;
        }
        if (this->length < that.length) *this = that;
    }

    MaxCount operator* (const MaxCount &that) {
        return {this->length * that.length, this->ways};
    }
    MaxCount& operator+=(const MaxCount &that) {
        this->length += that.length;
        this->ways *= that.ways;
        return *this;
    }

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

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


const int N = 5e5 + 100;
int n, leaf;
vector<int> e[N];
MaxCount f1[N], f2[N];

map<int, long long> total[N];
// vector<MaxCount> longest[N];

MaxCount dfsDown(int u, int p) {
    // f[u] = MaxCount(0, 1);
    total[u][0] = 1;
    for (int v : e[u]) if (v != p) {
        MaxCount curr = dfsDown(v, u) + MaxCount(1, 1);
        // longest[u].push_back(curr);
        total[u][curr.length] += curr.ways;
    }
    // if (total[u].size() == 1) ++leaf;
    // sort(longest[u].begin(), longest[u].end());
    // reverse(longest[u].begin(), longest[u].end());
    // cerr << "At " << u << '\n';
    // cerr << "All \n";
    // for (auto l : longest[u]) cerr << l;
    // cerr << "Longest:"  << MaxCount(*total[u].rbegin());
    return MaxCount(*total[u].rbegin());
}

MaxCount best(0, 1);
void dfsUp(int u, int p, MaxCount outOfSubtree) {
    // cerr << "Up at " << u << outOfSubtree;

    vector<MaxCount> pref1(e[u].size()), pref2(e[u].size()), suff1(e[u].size()), suff2(e[u].size()), f(e[u].size());
    // cerr << "F + Pref\n";
    for (int i = 0; i < e[u].size(); ++i) {
        int v = e[u][i];
        if (v != p) f[i] = MaxCount(*total[v].rbegin()) + MaxCount(1, 1);
        else f[i] = outOfSubtree;
        pref1[i] = f[i]; 
        if (i) {
            pref1[i].merge(pref1[i - 1]);
            pref2[i] = pref2[i - 1];
            pref2[i].merge(pref1[i - 1] + f[i]);
        }
        // cerr << i << ' ' << v << ' ' << f[i] << ' ' << pref1[i] << ' ' << pref2[i] << '\n';
    }
    // cerr << "Suff\n";
    for (int i = e[u].size() - 1; i >= 0; --i) {
        int v = e[u][i];
        suff1[i] = f[i];
        if (i + 1 < e[u].size()) {
            suff1[i].merge(suff1[i + 1]);
            suff2[i] = suff2[i + 1];
            suff2[i].merge(suff1[i + 1] + f[i]);
        }
        // cerr << i << ' ' << v << ' ' << suff1[i] << ' ' << suff2[i] << '\n';
    }

    for (int i = 0; i < e[u].size(); ++i) {
        int v = e[u][i];
        MaxCount curr;
        // (pref1, suff1) * v
        if (i && i + 1 < e[u].size()) {
            curr = (pref1[i - 1] + suff1[i + 1]) * f[i];
            // cerr << i << ' ' << v << ' ' << pref1[i - 1] << ' ' << suff1[i + 1] << ' ' << f[i] << ' ' << curr << '\n';
            best.merge(curr);
        }
        // (pref2) * v 
        if (i > 1) {
            curr = (pref2[i - 1]) * f[i];
            // cerr << i << ' ' << v << ' ' << pref2[i - 1] << ' ' << f[i] << ' ' << curr << '\n';
            best.merge(curr);
        }
        // (suff2) * v 
        if (i + 2 < e[u].size()) {
            curr = (suff2[i + 1]) * f[i];
            // cerr << i << ' ' << v << ' ' << suff2[i + 1] << ' ' << f[i] << ' ' << curr << '\n';
            best.merge(curr);
        }
    }
    for (int v : e[u]) if (v != p) {
        MaxCount curr(*total[v].rbegin());
        total[u][curr.length + 1] -= curr.ways;
        if (total[u][curr.length + 1] == 0) total[u].erase(curr.length + 1);
        MaxCount thisOutOfSubtree(outOfSubtree);
        thisOutOfSubtree.merge(MaxCount(*total[u].rbegin()));
        dfsUp(v, u, thisOutOfSubtree + MaxCount(1, 1));
        total[u][curr.length + 1] += curr.ways;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfsDown(1, -1);
    dfsUp(1, -1, {-N, 0});
    cout << best.length << ' ' << best.ways << '\n';
}

Compilation message (stderr)

road.cpp: In function 'void dfsUp(int, int, MaxCount)':
road.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < e[u].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
road.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if (i + 1 < e[u].size()) {
      |             ~~~~~~^~~~~~~~~~~~~
road.cpp:87:13: warning: unused variable 'v' [-Wunused-variable]
   87 |         int v = e[u][i];
      |             ^
road.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < e[u].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
road.cpp:101:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if (i && i + 1 < e[u].size()) {
      |                  ~~~~~~^~~~~~~~~~~~~
road.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         if (i + 2 < e[u].size()) {
      |             ~~~~~~^~~~~~~~~~~~~
road.cpp:98:13: warning: unused variable 'v' [-Wunused-variable]
   98 |         int v = e[u][i];
      |             ^

• Subtask 1: 0 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48