oj.uz

답안 #344457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344457 2021-01-05T20:00:29 Z apostoldaniel854 Hard route (IZhO17_road) C++14
0 / 100
 9 ms 12140 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
const int N = 5e5;

struct Best {
    ll mx;
    ll freq;
};
vector <int> gr[1 + N];

int n;
Best dpDown[1 + N], dpUp[1 + N];
void updateBest (Best &ans, Best cur) {
    if (cur.freq == 0) return;
    if (ans.mx < cur.mx) {
        ans = cur;
    }
    else if (ans.mx == cur.mx)
        ans.freq += cur.freq;
}

void dfsDown (int node, int par) {
    dpDown[node] = {0, 1};
    for (int son : gr[node])
        if (son != par) {
            dfsDown (son, node);
            updateBest (dpDown[node], {dpDown[son].mx + 1, dpDown[son].freq});
        }
}

Best pref[1 + N], suff[1 + N];

void dfsUp (int node, int par) {
    int sz = gr[node].size ();
    for (int i = 0; i < sz; i++) {
        int son = gr[node][i];
        pref[i] = {0, 0};
        if (i > 0)
            pref[i] = pref[i - 1];
        if (son != par)
            updateBest (pref[i], {dpDown[son].mx + 2, dpDown[son].freq});
    }
    for (int i = sz - 1; i >= 0; i--) {
        int son = gr[node][i];
        suff[i] = {0, 0};
        if (i < sz - 1)
            suff[i] = suff[i + 1];
        if (son != par)
            updateBest (suff[i], {dpDown[son].mx + 2, dpDown[son].freq});
    }
    for (int i = 0; i < sz; i++) {
        int son = gr[node][i];
        if (son != par) {
            updateBest (dpUp[son], {dpUp[node].mx + 1, dpUp[node].freq});
            if (i > 0)
                updateBest (dpUp[son], pref[i - 1]);
            if (i < sz - 1)
                updateBest (dpUp[son], suff[i + 1]);
            dfsUp (son, node);
        }
    }
}
bool cmp (Best a, Best b) {
    return a.mx > b.mx;
}

struct Help {
    ll mx;
    ll freq;
    ll cnt;
};
ll dp[3];
Best ans = {0, 1};
void solve (int node, int par) {
    vector <Best> edges;
    for (int son : gr[node])
        if (son != par)
            edges.pb ({dpDown[son].mx + 1, dpDown[son].freq});
    if (dpUp[node].mx > 0)
        edges.pb (dpUp[node]);

    sort (edges.begin (), edges.end (), cmp);
    while (edges.size () >= 3 && edges.back ().mx < edges[2].mx)
        edges.pop_back ();

    if (edges.size () >= 3) {
        vector <Help> good;
        for (int i = 0; i < edges.size (); i++) {
            int j = i;
            ll freq = 0;
            while (j < edges.size () && edges[i].mx == edges[j].mx) {
                freq += edges[j].freq;
                j++;
            }
            good.pb ({edges[i].mx, freq, j - i});
            i = j - 1;
        }
        if (good.size () == 1) {
            dp[1] = dp[2] = 0;
            for (Best edge : edges) {
                ll dp1 = dp[1] + edge.freq;
                ll dp2 = dp[2] + dp[1] * edge.freq;
                dp[1] = dp1; dp[2] = dp2;
            }
            updateBest (ans, {2 * good[0].mx * good[0].mx, dp[2]});
        }
        else if (good.size () == 2) {
            if (good[0].cnt > 1)
                updateBest (ans, {good[0].mx * (good[0].mx + good[1].mx), good[0].freq * good[1].freq});
            else {
                dp[1] = dp[2] = 0;
                for (Best edge : edges) {
                    if (edge.mx == good[1].mx) {
                        ll dp1 = dp[1] + edge.freq;
                        ll dp2 = dp[2] + dp[1] * edge.freq;
                        dp[1] = dp1; dp[2] = dp2;
                    }
                }
                updateBest (ans, {2 * good[0].mx * good[1].mx, dp[2]});
            }
        }
        else {
            updateBest (ans, {good[0].mx * (good[1].mx + good[2].mx), good[1].freq * good[2].freq});
        }
    }
    for (int son : gr[node])
        if (son != par)
            solve (son, node);
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        gr[y].pb (x);
    }
    int root = 0;
    for (int i = 1; i <= n; i++)
        if (gr[i].size () > 1)
            root = i;
    ans = {0, 1};
    if (root) {
        dfsDown (root, 0);
        dpUp[root] = {-n, 0};
        dfsUp (root, 0);
        solve (root, 0);
    }
    cout << ans.mx << " " << ans.freq;
    return 0;
}
/**
3 3
1 5 1
2 3
1 1 5
2 3
**/

Compilation message

road.cpp: In function 'void solve(int, int)':
road.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Best>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for (int i = 0; i < edges.size (); i++) {
      |                         ~~^~~~~~~~~~~~~~~
road.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Best>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             while (j < edges.size () && edges[i].mx == edges[j].mx) {
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 8 ms 12140 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 8 ms 12140 KB Output is correct
7 Correct 8 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 8 ms 12140 KB Output is correct
10 Correct 8 ms 12140 KB Output is correct
11 Incorrect 8 ms 12140 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 8 ms 12140 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 8 ms 12140 KB Output is correct
7 Correct 8 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 8 ms 12140 KB Output is correct
10 Correct 8 ms 12140 KB Output is correct
11 Incorrect 8 ms 12140 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 8 ms 12140 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 8 ms 12140 KB Output is correct
7 Correct 8 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 8 ms 12140 KB Output is correct
10 Correct 8 ms 12140 KB Output is correct
11 Incorrect 8 ms 12140 KB Output isn't correct
12 Halted 0 ms 0 KB -