oj.uz

Submission #35062

# Submission time Handle Problem Language Result Execution time Memory
35062 2017-11-17T20:52:18 Z model_code Hard route (IZhO17_road) C++11
100 / 100
 1279 ms 68684 KB 
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <sstream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define y1 stupid_cmath
#define left stupid_left
#define right stupid_right
#define vi vector <int>
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))

const int inf = (int)1e9;
const int mod = inf + 7;
const double eps = 1e-9;
const double pi = acos(-1.0);

inline void read(int &x)
{
    char c = '0'; c--;
    x = 0;
    while((c < '0' || c > '9')) c = getchar();
    while((c >= '0' && c <= '9')) x = x * 10 + c - '0', c = getchar();
}

int n;
vector<int> g[1001000];
int up[1001000], dp[1001000];
ll best = -inf, ans = -inf;
vector<int> goods;

void calc_dp(int v, int par) {
    dp[v] = 0;
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        calc_dp(to, v);
        dp[v] = max(dp[v], dp[to] + 1);
    }
}

void calc_up(int v, int par) {
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        up[to] = max(up[to], up[v] + 1);
    }
    int cur = -inf;
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        up[to] = max(up[to], cur + 2);
        cur = max(cur, dp[to]);
    }
    cur = -inf;
    for (int i = sz(g[v]) - 1; i >= 0; i--) {
        int to = g[v][i];
        if (to == par) continue;
        up[to] = max(up[to], cur + 2);
        cur = max(cur, dp[to]);
    }
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        calc_up(to, v);
    }
}

void calc_ans(int v, int par) {
    int data1 = -inf, data2 = -inf, data3 = -inf;
    if (par != -1) {
        if (up[v] > data1) {
            data3 = data2;
            data2 = data1;
            data1 = up[v];
        } else if (up[v] > data2) {
            data3 = data2;
            data2 = up[v];
        } else if (up[v] > data3) {
            data3 = up[v];
        }
    }
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        if (dp[to] + 1 > data1) {
            data3 = data2;
            data2 = data1;
            data1 = dp[to] + 1;
        } else if (dp[to] + 1 > data2) {
            data3 = data2;
            data2 = dp[to] + 1;
        } else if (dp[to] + 1 > data3) {
            data3 = dp[to] + 1;
        }
    }
    if (data3 != -inf) {
        int mx3 = data3;
        int mx2 = data2;
        int mx1 = data1;
        ll val = (mx2 + mx3) * 1ll * mx1;
        if (val > best) {
            best = val;
            goods.clear();
            goods.pb(v);
        } else if (val == best) {
            goods.pb(v);
        }
    }
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        calc_ans(to, v);
    }
}

void dfs(int v, int par, int deg, int &mx, int &cnt) {
    if (deg > mx) {
        mx = deg;
        cnt = 1;
    } else if (deg == mx) cnt++;
    forit (it, g[v]) {
        int to = *it;
        if (to != par) dfs(to, v, deg + 1, mx, cnt);
    }
}

void process(int root) {
    vector<pii> v;
    for (int i = 0; i < g[root].size(); i++) {
        int child = g[root][i];
        int mx = -1, cnt = -1;
        dfs(child, root, 1, mx, cnt);
        v.pb(mp(mx, cnt));
    }
    assert(v.size() >= 3);
    int mx1 = -inf, mx2 = -inf, mx3 = -inf;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].f > mx1) {
            mx3 = mx2;
            mx2 = mx1;
            mx1 = v[i].f;
        } else if (v[i].f > mx2) {
            mx3 = mx2;
            mx2 = v[i].f;
        } else if (v[i].f > mx3) {
            mx3 = v[i].f;
        }
    }
    ll s2 = 0, s = 0, q = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].f == mx3) {
            s2 += v[i].s * 1ll * v[i].s;
            s += v[i].s;
        }
        if (v[i].f == mx2) {
            q += v[i].s;
        }
    }
    if (mx2 == mx3) {
        ans += (s * s - s2) / 2;
    } else {
        ans += s * q;
    }
}

int main(){
    
    
    read(n);
    for (int i = 0, x, y; i < n - 1; i++) {
        read(x);
        read(y);
        x--; y--;
        g[x].pb(y);
        g[y].pb(x);
    }
    
    int leaf_number = 0;
    for (int i = 0; i < n; i++) {
        if (g[i].size() == 1) leaf_number++;
    }
    
    if (leaf_number == 2) {
        printf("0 1\n");
        return 0;
    }
    
    calc_dp(0, -1);

    calc_up(0, -1);

    calc_ans(0, -1);

    ans = 0;
    for (int i = 0; i < goods.size(); i++) {
        process(goods[i]);
    }

    printf("%lld %lld\n", best, ans);
    
    return 0;
}

Compilation message

road.cpp: In function 'void process(int)':
road.cpp:155:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[root].size(); i++) {
                       ^
road.cpp:163:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                       ^
road.cpp:176:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                       ^
road.cpp: In function 'int main()':
road.cpp:221:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < goods.size(); i++) {
                       ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33300 KB Output is correct
2 Correct 9 ms 33300 KB Output is correct
3 Correct 9 ms 33300 KB Output is correct
4 Correct 3 ms 33300 KB Output is correct
5 Correct 16 ms 33300 KB Output is correct
6 Correct 3 ms 33300 KB Output is correct
7 Correct 3 ms 33300 KB Output is correct
8 Correct 6 ms 33300 KB Output is correct
9 Correct 6 ms 33300 KB Output is correct
10 Correct 3 ms 33300 KB Output is correct
11 Correct 9 ms 33300 KB Output is correct
12 Correct 3 ms 33300 KB Output is correct
13 Correct 6 ms 33300 KB Output is correct
14 Correct 13 ms 33300 KB Output is correct
15 Correct 3 ms 33300 KB Output is correct
16 Correct 9 ms 33300 KB Output is correct
17 Correct 6 ms 33300 KB Output is correct
18 Correct 6 ms 33300 KB Output is correct
19 Correct 3 ms 33300 KB Output is correct
20 Correct 6 ms 33300 KB Output is correct
21 Correct 3 ms 33300 KB Output is correct
22 Correct 6 ms 33300 KB Output is correct
23 Correct 6 ms 33300 KB Output is correct
24 Correct 9 ms 33300 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33300 KB Output is correct
2 Correct 9 ms 33300 KB Output is correct
3 Correct 9 ms 33300 KB Output is correct
4 Correct 3 ms 33300 KB Output is correct
5 Correct 16 ms 33300 KB Output is correct
6 Correct 3 ms 33300 KB Output is correct
7 Correct 3 ms 33300 KB Output is correct
8 Correct 6 ms 33300 KB Output is correct
9 Correct 6 ms 33300 KB Output is correct
10 Correct 3 ms 33300 KB Output is correct
11 Correct 9 ms 33300 KB Output is correct
12 Correct 3 ms 33300 KB Output is correct
13 Correct 6 ms 33300 KB Output is correct
14 Correct 13 ms 33300 KB Output is correct
15 Correct 3 ms 33300 KB Output is correct
16 Correct 9 ms 33300 KB Output is correct
17 Correct 6 ms 33300 KB Output is correct
18 Correct 6 ms 33300 KB Output is correct
19 Correct 3 ms 33300 KB Output is correct
20 Correct 6 ms 33300 KB Output is correct
21 Correct 3 ms 33300 KB Output is correct
22 Correct 6 ms 33300 KB Output is correct
23 Correct 6 ms 33300 KB Output is correct
24 Correct 9 ms 33300 KB Output is correct
25 Correct 6 ms 33500 KB Output is correct
26 Correct 9 ms 33500 KB Output is correct
27 Correct 9 ms 33504 KB Output is correct
28 Correct 6 ms 33500 KB Output is correct
29 Correct 3 ms 33432 KB Output is correct
30 Correct 6 ms 33440 KB Output is correct
31 Correct 13 ms 33440 KB Output is correct
32 Correct 9 ms 33432 KB Output is correct
33 Correct 3 ms 33504 KB Output is correct
34 Correct 16 ms 33504 KB Output is correct
35 Correct 9 ms 33500 KB Output is correct
36 Correct 3 ms 33504 KB Output is correct
37 Correct 3 ms 33432 KB Output is correct
38 Correct 3 ms 33432 KB Output is correct
39 Correct 9 ms 33432 KB Output is correct
40 Correct 6 ms 33432 KB Output is correct
41 Correct 13 ms 33432 KB Output is correct
42 Correct 13 ms 33432 KB Output is correct
43 Correct 3 ms 33432 KB Output is correct
44 Correct 9 ms 33432 KB Output is correct
45 Correct 9 ms 33432 KB Output is correct
46 Correct 9 ms 33432 KB Output is correct
47 Correct 9 ms 33576 KB Output is correct
48 Correct 9 ms 33564 KB Output is correct

Subtask #3
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33300 KB Output is correct
2 Correct 9 ms 33300 KB Output is correct
3 Correct 9 ms 33300 KB Output is correct
4 Correct 3 ms 33300 KB Output is correct
5 Correct 16 ms 33300 KB Output is correct
6 Correct 3 ms 33300 KB Output is correct
7 Correct 3 ms 33300 KB Output is correct
8 Correct 6 ms 33300 KB Output is correct
9 Correct 6 ms 33300 KB Output is correct
10 Correct 3 ms 33300 KB Output is correct
11 Correct 9 ms 33300 KB Output is correct
12 Correct 3 ms 33300 KB Output is correct
13 Correct 6 ms 33300 KB Output is correct
14 Correct 13 ms 33300 KB Output is correct
15 Correct 3 ms 33300 KB Output is correct
16 Correct 9 ms 33300 KB Output is correct
17 Correct 6 ms 33300 KB Output is correct
18 Correct 6 ms 33300 KB Output is correct
19 Correct 3 ms 33300 KB Output is correct
20 Correct 6 ms 33300 KB Output is correct
21 Correct 3 ms 33300 KB Output is correct
22 Correct 6 ms 33300 KB Output is correct
23 Correct 6 ms 33300 KB Output is correct
24 Correct 9 ms 33300 KB Output is correct
25 Correct 6 ms 33500 KB Output is correct
26 Correct 9 ms 33500 KB Output is correct
27 Correct 9 ms 33504 KB Output is correct
28 Correct 6 ms 33500 KB Output is correct
29 Correct 3 ms 33432 KB Output is correct
30 Correct 6 ms 33440 KB Output is correct
31 Correct 13 ms 33440 KB Output is correct
32 Correct 9 ms 33432 KB Output is correct
33 Correct 3 ms 33504 KB Output is correct
34 Correct 16 ms 33504 KB Output is correct
35 Correct 9 ms 33500 KB Output is correct
36 Correct 3 ms 33504 KB Output is correct
37 Correct 3 ms 33432 KB Output is correct
38 Correct 3 ms 33432 KB Output is correct
39 Correct 9 ms 33432 KB Output is correct
40 Correct 6 ms 33432 KB Output is correct
41 Correct 13 ms 33432 KB Output is correct
42 Correct 13 ms 33432 KB Output is correct
43 Correct 3 ms 33432 KB Output is correct
44 Correct 9 ms 33432 KB Output is correct
45 Correct 9 ms 33432 KB Output is correct
46 Correct 9 ms 33432 KB Output is correct
47 Correct 9 ms 33576 KB Output is correct
48 Correct 9 ms 33564 KB Output is correct
49 Correct 779 ms 68680 KB Output is correct
50 Correct 796 ms 68684 KB Output is correct
51 Correct 813 ms 68676 KB Output is correct
52 Correct 813 ms 68676 KB Output is correct
53 Correct 579 ms 61452 KB Output is correct
54 Correct 593 ms 63488 KB Output is correct
55 Correct 629 ms 58520 KB Output is correct
56 Correct 633 ms 60640 KB Output is correct
57 Correct 776 ms 68284 KB Output is correct
58 Correct 766 ms 68284 KB Output is correct
59 Correct 736 ms 68280 KB Output is correct
60 Correct 703 ms 68284 KB Output is correct
61 Correct 456 ms 48876 KB Output is correct
62 Correct 509 ms 48876 KB Output is correct
63 Correct 1279 ms 57708 KB Output is correct
64 Correct 1223 ms 53796 KB Output is correct
65 Correct 1249 ms 51268 KB Output is correct
66 Correct 1126 ms 49960 KB Output is correct
67 Correct 1116 ms 49232 KB Output is correct
68 Correct 1149 ms 48948 KB Output is correct
69 Correct 1113 ms 48876 KB Output is correct
70 Correct 1153 ms 48876 KB Output is correct
71 Correct 1073 ms 48876 KB Output is correct
72 Correct 1119 ms 49008 KB Output is correct
73 Correct 1093 ms 49192 KB Output is correct
74 Correct 1116 ms 49524 KB Output is correct
75 Correct 1046 ms 50036 KB Output is correct
76 Correct 949 ms 51060 KB Output is correct
77 Correct 749 ms 53108 KB Output is correct
78 Correct 433 ms 57204 KB Output is correct