답안 #35062 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
35062	2017-11-17T20:52:18 Z	model_code	Hard route (IZhO17_road)	C++11	100 / 100	1279 ms	68684 KB

road

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #35062

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 33.0 / 33.0

Subtask #3 48.0 / 48.0

Subtask #1
19.0 / 19.0

Subtask #2
33.0 / 33.0

Subtask #3
48.0 / 48.0