oj.uz

Submission #343924

# Submission time Handle Problem Language Result Execution time Memory
343924 2021-01-04T18:35:41 Z Sprdalo Hard route (IZhO17_road) C++17
0 / 100
 22 ms 35692 KB 
#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

const int maxn = 5e5+5;
vi e[maxn], p(maxn);
vp dp[maxn], d(maxn, {0,1});

void update_pi(pi& a, pi b){
    if (a.first == b.first)
        a.second += b.second;
    if (a.first < b.first)
        a = b;
}

pi dfs(int x, int st){
    pi q = {0, 1};
    for (auto& i : e[x]){
        if (i == st){
            p[x] = i;
            continue;
        }

        pi y = dfs(i, x);
        ++y.first;

        update_pi(q, y);

        dp[x].push_back(y);
    }

    if (q.first == 0)
        dp[x].push_back(q);

    return q;
}

void calc(int x){
    pi q = *max_element(dp[x].begin(), dp[x].end());

    pi t = q; t.second = 0;
    for (int i = 0; i < dp[x].size(); ++i){
        update_pi(t, dp[x][i]);
    }

    pi s = {0,1};
    for (int i = 0; i < dp[x].size(); ++i){
        if (dp[x][i].first == t.first) continue;
        update_pi(s, dp[x][i]);
    }

    int cur = 0;
    for (auto& i : e[x]){
        if (p[x] == i) continue;

        if (dp[x][cur].first == t.first && dp[x][cur].second == t.second){
            d[i] = d[x]; d[i].first++;
            if (s.first>0)
            update_pi(d[i], {s.first+1, s.second});
        } else {
            pi tmp = t;
            if (dp[x][cur].first == t.first)
                tmp.second -= dp[x][cur].second;
            d[i] = d[x]; d[i].first++;
            update_pi(d[i], {tmp.first+1, tmp.second});
        }

        calc(i);
        ++cur;
    }
}

pi sol = {0, 1};
void solve(int x){
    int len = dp[x].size();
    if ((len >= 2 && d[x].first > 0) || len >= 3){
        pi a = {0, 1}, b = {0,1}, c = {0, 1};
        dp[x].push_back(d[x]);

       // sort(dp[x].rbegin(), dp[x].rend());
        //a = dp[x][0]; b = dp[x][1]; c = dp[x][2];
        for (pi t : dp[x]){
            if (t.first > a.first){
                swap(b, c);
                swap(a, b);
                a = t;
                continue;
            }

            if (t.first > b.first){
                swap(b, c);
                b = t;
                continue;
            }

            if (t.first > c.first)
                c = t;
        }    

        int cnt = 0, cc = 0;
        for (pi t : dp[x]){
            if (t.first == c.first){
                ++cc;
                cnt += t.second;
            }
        }

        //cout << x << ' ' << a.first << ' ' << b.first << ' ' << c.first << ' ';
        pi res = {a.first * (b.first + c.first), 0};
        //if (res.first == 1980) cout << "BRATE " << a.first << ' ' << b.first << ' ' << c.first << ' ' << d[x].first << '\n';
        //cout << res.first << ' ';
        if (a.first == b.first && a.first == c.first){
       //     if (res.first == 2) cout << "PRVI\n";
            for (pi t : dp[x]){
                if (t.first != c.first) continue;
                res.second += (cc - 2) * t.second * (cnt - t.second);
            }
            //res.second *=2;
          //  res.second /= 3;
        }

        if (a.first == b.first && b.first != c.first){
         //   if (res.first == 2) cout << "DRUGI\n";
            res.second = (b.second+a.second) * cnt;
        }

        if (a.first != b.first && b.first == c.first){
           // if (res.first == 2) cout << "TRECI\n";
            for (pi t : dp[x])
                if (t.first == c.first)
                    res.second += t.second * (cnt - t.second);
        }

        if (a.first != b.first && b.first != c.first){
    //        if (res.first == 2) cout << "CETRI\n";
            res.second = b.second * cnt;
            res.second *= 2;
        }

        res.second /= 2;
      //  if (res.first == 2)
        //    cout <<res.second << '\n';
        //cout << res.second << '\n';
        update_pi(sol, res);
    }

    for (auto& i : e[x]){
        if (i != p[x])
            solve(i);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n;
    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);
    }

    dfs(1, 1);
    calc(1);
    solve(1);

    cout << sol.first << ' ' << sol.second << '\n';
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7
*/

Compilation message

road.cpp: In function 'void calc(ll)':
road.cpp:56:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < dp[x].size(); ++i){
      |                     ~~^~~~~~~~~~~~~~
road.cpp:61:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < dp[x].size(); ++i){
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35564 KB Output is correct
2 Correct 21 ms 35564 KB Output is correct
3 Correct 21 ms 35584 KB Output is correct
4 Correct 20 ms 35564 KB Output is correct
5 Correct 20 ms 35564 KB Output is correct
6 Correct 20 ms 35564 KB Output is correct
7 Correct 22 ms 35564 KB Output is correct
8 Correct 20 ms 35564 KB Output is correct
9 Correct 20 ms 35564 KB Output is correct
10 Correct 21 ms 35564 KB Output is correct
11 Correct 21 ms 35564 KB Output is correct
12 Correct 20 ms 35564 KB Output is correct
13 Correct 20 ms 35692 KB Output is correct
14 Correct 22 ms 35692 KB Output is correct
15 Correct 21 ms 35564 KB Output is correct
16 Correct 20 ms 35564 KB Output is correct
17 Correct 20 ms 35564 KB Output is correct
18 Correct 20 ms 35564 KB Output is correct
19 Correct 21 ms 35564 KB Output is correct
20 Correct 21 ms 35564 KB Output is correct
21 Incorrect 20 ms 35564 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35564 KB Output is correct
2 Correct 21 ms 35564 KB Output is correct
3 Correct 21 ms 35584 KB Output is correct
4 Correct 20 ms 35564 KB Output is correct
5 Correct 20 ms 35564 KB Output is correct
6 Correct 20 ms 35564 KB Output is correct
7 Correct 22 ms 35564 KB Output is correct
8 Correct 20 ms 35564 KB Output is correct
9 Correct 20 ms 35564 KB Output is correct
10 Correct 21 ms 35564 KB Output is correct
11 Correct 21 ms 35564 KB Output is correct
12 Correct 20 ms 35564 KB Output is correct
13 Correct 20 ms 35692 KB Output is correct
14 Correct 22 ms 35692 KB Output is correct
15 Correct 21 ms 35564 KB Output is correct
16 Correct 20 ms 35564 KB Output is correct
17 Correct 20 ms 35564 KB Output is correct
18 Correct 20 ms 35564 KB Output is correct
19 Correct 21 ms 35564 KB Output is correct
20 Correct 21 ms 35564 KB Output is correct
21 Incorrect 20 ms 35564 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35564 KB Output is correct
2 Correct 21 ms 35564 KB Output is correct
3 Correct 21 ms 35584 KB Output is correct
4 Correct 20 ms 35564 KB Output is correct
5 Correct 20 ms 35564 KB Output is correct
6 Correct 20 ms 35564 KB Output is correct
7 Correct 22 ms 35564 KB Output is correct
8 Correct 20 ms 35564 KB Output is correct
9 Correct 20 ms 35564 KB Output is correct
10 Correct 21 ms 35564 KB Output is correct
11 Correct 21 ms 35564 KB Output is correct
12 Correct 20 ms 35564 KB Output is correct
13 Correct 20 ms 35692 KB Output is correct
14 Correct 22 ms 35692 KB Output is correct
15 Correct 21 ms 35564 KB Output is correct
16 Correct 20 ms 35564 KB Output is correct
17 Correct 20 ms 35564 KB Output is correct
18 Correct 20 ms 35564 KB Output is correct
19 Correct 21 ms 35564 KB Output is correct
20 Correct 21 ms 35564 KB Output is correct
21 Incorrect 20 ms 35564 KB Output isn't correct
22 Halted 0 ms 0 KB -