oj.uz

Submission #447115

# Submission time Handle Problem Language Result Execution time Memory
447115 2021-07-24T14:57:43 Z nickyrio Hard route (IZhO17_road) C++17
0 / 100
 27 ms 51312 KB 
#include <bits/stdc++.h>

using namespace std;

struct MaxCount {
    long long length;
    long long ways;

    MaxCount(): length(0), ways(0) {}
    MaxCount(long long 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<long long, 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 25 ms 51148 KB Output is correct
2 Correct 25 ms 51144 KB Output is correct
3 Correct 26 ms 51108 KB Output is correct
4 Correct 26 ms 51136 KB Output is correct
5 Correct 26 ms 51136 KB Output is correct
6 Correct 26 ms 51148 KB Output is correct
7 Correct 26 ms 51148 KB Output is correct
8 Correct 26 ms 51232 KB Output is correct
9 Correct 26 ms 51244 KB Output is correct
10 Correct 27 ms 51148 KB Output is correct
11 Correct 26 ms 51152 KB Output is correct
12 Correct 26 ms 51092 KB Output is correct
13 Correct 26 ms 51228 KB Output is correct
14 Correct 26 ms 51312 KB Output is correct
15 Correct 27 ms 51220 KB Output is correct
16 Correct 26 ms 51180 KB Output is correct
17 Correct 27 ms 51168 KB Output is correct
18 Correct 27 ms 51208 KB Output is correct
19 Correct 25 ms 51264 KB Output is correct
20 Correct 27 ms 51308 KB Output is correct
21 Incorrect 26 ms 51276 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 51148 KB Output is correct
2 Correct 25 ms 51144 KB Output is correct
3 Correct 26 ms 51108 KB Output is correct
4 Correct 26 ms 51136 KB Output is correct
5 Correct 26 ms 51136 KB Output is correct
6 Correct 26 ms 51148 KB Output is correct
7 Correct 26 ms 51148 KB Output is correct
8 Correct 26 ms 51232 KB Output is correct
9 Correct 26 ms 51244 KB Output is correct
10 Correct 27 ms 51148 KB Output is correct
11 Correct 26 ms 51152 KB Output is correct
12 Correct 26 ms 51092 KB Output is correct
13 Correct 26 ms 51228 KB Output is correct
14 Correct 26 ms 51312 KB Output is correct
15 Correct 27 ms 51220 KB Output is correct
16 Correct 26 ms 51180 KB Output is correct
17 Correct 27 ms 51168 KB Output is correct
18 Correct 27 ms 51208 KB Output is correct
19 Correct 25 ms 51264 KB Output is correct
20 Correct 27 ms 51308 KB Output is correct
21 Incorrect 26 ms 51276 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 51148 KB Output is correct
2 Correct 25 ms 51144 KB Output is correct
3 Correct 26 ms 51108 KB Output is correct
4 Correct 26 ms 51136 KB Output is correct
5 Correct 26 ms 51136 KB Output is correct
6 Correct 26 ms 51148 KB Output is correct
7 Correct 26 ms 51148 KB Output is correct
8 Correct 26 ms 51232 KB Output is correct
9 Correct 26 ms 51244 KB Output is correct
10 Correct 27 ms 51148 KB Output is correct
11 Correct 26 ms 51152 KB Output is correct
12 Correct 26 ms 51092 KB Output is correct
13 Correct 26 ms 51228 KB Output is correct
14 Correct 26 ms 51312 KB Output is correct
15 Correct 27 ms 51220 KB Output is correct
16 Correct 26 ms 51180 KB Output is correct
17 Correct 27 ms 51168 KB Output is correct
18 Correct 27 ms 51208 KB Output is correct
19 Correct 25 ms 51264 KB Output is correct
20 Correct 27 ms 51308 KB Output is correct
21 Incorrect 26 ms 51276 KB Output isn't correct
22 Halted 0 ms 0 KB -