oj.uz

Submission #447114

# Submission time Handle Problem Language Result Execution time Memory
447114 2021-07-24T14:56:25 Z nickyrio Hard route (IZhO17_road) C++17
0 / 100
 27 ms 51268 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51148 KB Output is correct
2 Correct 26 ms 51208 KB Output is correct
3 Correct 25 ms 51144 KB Output is correct
4 Correct 26 ms 51144 KB Output is correct
5 Correct 26 ms 51188 KB Output is correct
6 Correct 25 ms 51200 KB Output is correct
7 Correct 26 ms 51208 KB Output is correct
8 Correct 25 ms 51128 KB Output is correct
9 Correct 26 ms 51148 KB Output is correct
10 Correct 26 ms 51236 KB Output is correct
11 Correct 26 ms 51220 KB Output is correct
12 Correct 26 ms 51200 KB Output is correct
13 Correct 25 ms 51224 KB Output is correct
14 Correct 26 ms 51232 KB Output is correct
15 Correct 26 ms 51148 KB Output is correct
16 Correct 27 ms 51212 KB Output is correct
17 Correct 25 ms 51128 KB Output is correct
18 Correct 26 ms 51180 KB Output is correct
19 Correct 26 ms 51188 KB Output is correct
20 Correct 26 ms 51200 KB Output is correct
21 Incorrect 26 ms 51268 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51148 KB Output is correct
2 Correct 26 ms 51208 KB Output is correct
3 Correct 25 ms 51144 KB Output is correct
4 Correct 26 ms 51144 KB Output is correct
5 Correct 26 ms 51188 KB Output is correct
6 Correct 25 ms 51200 KB Output is correct
7 Correct 26 ms 51208 KB Output is correct
8 Correct 25 ms 51128 KB Output is correct
9 Correct 26 ms 51148 KB Output is correct
10 Correct 26 ms 51236 KB Output is correct
11 Correct 26 ms 51220 KB Output is correct
12 Correct 26 ms 51200 KB Output is correct
13 Correct 25 ms 51224 KB Output is correct
14 Correct 26 ms 51232 KB Output is correct
15 Correct 26 ms 51148 KB Output is correct
16 Correct 27 ms 51212 KB Output is correct
17 Correct 25 ms 51128 KB Output is correct
18 Correct 26 ms 51180 KB Output is correct
19 Correct 26 ms 51188 KB Output is correct
20 Correct 26 ms 51200 KB Output is correct
21 Incorrect 26 ms 51268 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51148 KB Output is correct
2 Correct 26 ms 51208 KB Output is correct
3 Correct 25 ms 51144 KB Output is correct
4 Correct 26 ms 51144 KB Output is correct
5 Correct 26 ms 51188 KB Output is correct
6 Correct 25 ms 51200 KB Output is correct
7 Correct 26 ms 51208 KB Output is correct
8 Correct 25 ms 51128 KB Output is correct
9 Correct 26 ms 51148 KB Output is correct
10 Correct 26 ms 51236 KB Output is correct
11 Correct 26 ms 51220 KB Output is correct
12 Correct 26 ms 51200 KB Output is correct
13 Correct 25 ms 51224 KB Output is correct
14 Correct 26 ms 51232 KB Output is correct
15 Correct 26 ms 51148 KB Output is correct
16 Correct 27 ms 51212 KB Output is correct
17 Correct 25 ms 51128 KB Output is correct
18 Correct 26 ms 51180 KB Output is correct
19 Correct 26 ms 51188 KB Output is correct
20 Correct 26 ms 51200 KB Output is correct
21 Incorrect 26 ms 51268 KB Output isn't correct
22 Halted 0 ms 0 KB -