답안 #35065 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
35065	2017-11-17T20:55:36 Z	model_code	Hard route (IZhO17_road)	C++11	100 / 100	1356 ms	82184 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];
pii up[1001000], dp[1001000];
ll best = -inf, ans = -inf;
vector<int> goods;

void update(pii &a, int x, int y) {
    if (x < 0) return;
    if (x > a.f) a = mp(x, y);
    else if (x == a.f) a.s += y;
}

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

void calc_up(int v, int par) {
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        up[to] = mp(0, 1);
        update(up[to], up[v].f + 1, up[v].s);
    }
    pii cur = mp(-inf, -inf);
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        update(up[to], cur.f + 2, cur.s);
        update(cur, dp[to].f, dp[to].s);
    }
    reverse(all(g[v]));
    cur = mp(-inf, -inf);
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        update(up[to], cur.f + 2, cur.s);
        update(cur, dp[to].f, dp[to].s);
    }
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        calc_up(to, v);
    }
}

int get_cnt(int v, int par, ll val) {
    int res = 0;
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        if (dp[to].f + 1 == val) res += dp[to].s;
    }
    return res;
}

ll calc_sum_of_pairwise_sum(int v, int par, ll val) {
    ll res2 = 0, res1 = 0;
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        if (dp[to].f + 1 == val) {
            res2 += dp[to].s * 1ll * dp[to].s;
            res1 += dp[to].s;
        }
    }
    return (res1 * res1 - res2) / 2;
}

void update(pii &a, pii &b, pii &c, int x, int y) {
    if (x > a.f) {
        c = b;
        b = a;
        a = mp(x, y);
    } else if (x > b.f) {
        c = b;
        b = mp(x, y);
    } else if (x > c.f) {
        c = mp(x, y);
    }
}

void calc_ans(int v, int par) {
    pii data1 = mp(-inf, -inf);
    pii data2 = mp(-inf, -inf);
    pii data3 = mp(-inf, -inf);
    if (par != -1) update(data1, data2, data3, up[v].f, up[v].s);
    forit (it, g[v]) {
        int to = *it;
        if (to == par) continue;
        update(data1, data2, data3, dp[to].f + 1, dp[to].s);
    }
    if (data3.f != -inf) {
        int mx3 = data3.f, cnt3 = data3.s;
        int mx2 = data2.f, cnt2 = data2.s;
        int mx1 = data1.f, cnt1 = data1.s;
        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 process(int root) {
    int par = -1;
    calc_dp(root, -1);
    pii data1 = mp(-inf, -inf);
    pii data2 = mp(-inf, -inf);
    pii data3 = mp(-inf, -inf);
    forit (it, g[root]) {
        int to = *it;
        if (to == par) continue;
        update(data1, data2, data3, dp[to].f + 1, dp[to].s);
    }
    int mx3 = data3.f, cnt3 = data3.s;
    int mx2 = data2.f, cnt2 = data2.s;
    int mx1 = data1.f, cnt1 = data1.s;
    ll res = 0;
    if (mx1 != mx2 && mx2 != mx3) {
        cnt3 = get_cnt(root, par, mx3);
        res = cnt2 * cnt3;
    } else if (mx1 != mx2 && mx2 == mx3) {
        res = calc_sum_of_pairwise_sum(root, par, mx3);
    } else if (mx1 == mx2 && mx2 != mx3) {
        cnt3 = get_cnt(root, par, mx3);
        res = (cnt1 + cnt2) * cnt3;
    } else if (mx1 == mx2 && mx2 == mx3) {
        res = calc_sum_of_pairwise_sum(root, par, mx3);
    } else {
        assert(false);
    }
    ans += res;
}

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);
    up[0] = mp(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 calc_ans(int, int)':
road.cpp:149:28: warning: unused variable 'cnt3' [-Wunused-variable]
         int mx3 = data3.f, cnt3 = data3.s;
                            ^
road.cpp:150:28: warning: unused variable 'cnt2' [-Wunused-variable]
         int mx2 = data2.f, cnt2 = data2.s;
                            ^
road.cpp:151:28: warning: unused variable 'cnt1' [-Wunused-variable]
         int mx1 = data1.f, cnt1 = data1.s;
                            ^
road.cpp: In function 'int main()':
road.cpp:226: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	41120 KB	Output is correct
2	Correct	9 ms	41120 KB	Output is correct
3	Correct	6 ms	41120 KB	Output is correct
4	Correct	13 ms	41120 KB	Output is correct
5	Correct	3 ms	41120 KB	Output is correct
6	Correct	9 ms	41120 KB	Output is correct
7	Correct	6 ms	41120 KB	Output is correct
8	Correct	9 ms	41120 KB	Output is correct
9	Correct	9 ms	41120 KB	Output is correct
10	Correct	3 ms	41120 KB	Output is correct
11	Correct	6 ms	41120 KB	Output is correct
12	Correct	3 ms	41120 KB	Output is correct
13	Correct	13 ms	41120 KB	Output is correct
14	Correct	6 ms	41120 KB	Output is correct
15	Correct	6 ms	41120 KB	Output is correct
16	Correct	3 ms	41120 KB	Output is correct
17	Correct	6 ms	41120 KB	Output is correct
18	Correct	3 ms	41120 KB	Output is correct
19	Correct	6 ms	41120 KB	Output is correct
20	Correct	9 ms	41120 KB	Output is correct
21	Correct	6 ms	41120 KB	Output is correct
22	Correct	9 ms	41120 KB	Output is correct
23	Correct	6 ms	41120 KB	Output is correct
24	Correct	13 ms	41120 KB	Output is correct

Subtask #2
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	41120 KB	Output is correct
2	Correct	9 ms	41120 KB	Output is correct
3	Correct	6 ms	41120 KB	Output is correct
4	Correct	13 ms	41120 KB	Output is correct
5	Correct	3 ms	41120 KB	Output is correct
6	Correct	9 ms	41120 KB	Output is correct
7	Correct	6 ms	41120 KB	Output is correct
8	Correct	9 ms	41120 KB	Output is correct
9	Correct	9 ms	41120 KB	Output is correct
10	Correct	3 ms	41120 KB	Output is correct
11	Correct	6 ms	41120 KB	Output is correct
12	Correct	3 ms	41120 KB	Output is correct
13	Correct	13 ms	41120 KB	Output is correct
14	Correct	6 ms	41120 KB	Output is correct
15	Correct	6 ms	41120 KB	Output is correct
16	Correct	3 ms	41120 KB	Output is correct
17	Correct	6 ms	41120 KB	Output is correct
18	Correct	3 ms	41120 KB	Output is correct
19	Correct	6 ms	41120 KB	Output is correct
20	Correct	9 ms	41120 KB	Output is correct
21	Correct	6 ms	41120 KB	Output is correct
22	Correct	9 ms	41120 KB	Output is correct
23	Correct	6 ms	41120 KB	Output is correct
24	Correct	13 ms	41120 KB	Output is correct
25	Correct	9 ms	41280 KB	Output is correct
26	Correct	6 ms	41332 KB	Output is correct
27	Correct	9 ms	41364 KB	Output is correct
28	Correct	9 ms	41364 KB	Output is correct
29	Correct	6 ms	41304 KB	Output is correct
30	Correct	3 ms	41332 KB	Output is correct
31	Correct	6 ms	41332 KB	Output is correct
32	Correct	3 ms	41280 KB	Output is correct
33	Correct	6 ms	41324 KB	Output is correct
34	Correct	9 ms	41376 KB	Output is correct
35	Correct	6 ms	41364 KB	Output is correct
36	Correct	6 ms	41340 KB	Output is correct
37	Correct	3 ms	41252 KB	Output is correct
38	Correct	9 ms	41252 KB	Output is correct
39	Correct	13 ms	41280 KB	Output is correct
40	Correct	9 ms	41252 KB	Output is correct
41	Correct	6 ms	41252 KB	Output is correct
42	Correct	9 ms	41252 KB	Output is correct
43	Correct	13 ms	41252 KB	Output is correct
44	Correct	6 ms	41252 KB	Output is correct
45	Correct	13 ms	41252 KB	Output is correct
46	Correct	13 ms	41252 KB	Output is correct
47	Correct	13 ms	41252 KB	Output is correct
48	Correct	13 ms	41384 KB	Output is correct

Subtask #3
48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	41120 KB	Output is correct
2	Correct	9 ms	41120 KB	Output is correct
3	Correct	6 ms	41120 KB	Output is correct
4	Correct	13 ms	41120 KB	Output is correct
5	Correct	3 ms	41120 KB	Output is correct
6	Correct	9 ms	41120 KB	Output is correct
7	Correct	6 ms	41120 KB	Output is correct
8	Correct	9 ms	41120 KB	Output is correct
9	Correct	9 ms	41120 KB	Output is correct
10	Correct	3 ms	41120 KB	Output is correct
11	Correct	6 ms	41120 KB	Output is correct
12	Correct	3 ms	41120 KB	Output is correct
13	Correct	13 ms	41120 KB	Output is correct
14	Correct	6 ms	41120 KB	Output is correct
15	Correct	6 ms	41120 KB	Output is correct
16	Correct	3 ms	41120 KB	Output is correct
17	Correct	6 ms	41120 KB	Output is correct
18	Correct	3 ms	41120 KB	Output is correct
19	Correct	6 ms	41120 KB	Output is correct
20	Correct	9 ms	41120 KB	Output is correct
21	Correct	6 ms	41120 KB	Output is correct
22	Correct	9 ms	41120 KB	Output is correct
23	Correct	6 ms	41120 KB	Output is correct
24	Correct	13 ms	41120 KB	Output is correct
25	Correct	9 ms	41280 KB	Output is correct
26	Correct	6 ms	41332 KB	Output is correct
27	Correct	9 ms	41364 KB	Output is correct
28	Correct	9 ms	41364 KB	Output is correct
29	Correct	6 ms	41304 KB	Output is correct
30	Correct	3 ms	41332 KB	Output is correct
31	Correct	6 ms	41332 KB	Output is correct
32	Correct	3 ms	41280 KB	Output is correct
33	Correct	6 ms	41324 KB	Output is correct
34	Correct	9 ms	41376 KB	Output is correct
35	Correct	6 ms	41364 KB	Output is correct
36	Correct	6 ms	41340 KB	Output is correct
37	Correct	3 ms	41252 KB	Output is correct
38	Correct	9 ms	41252 KB	Output is correct
39	Correct	13 ms	41280 KB	Output is correct
40	Correct	9 ms	41252 KB	Output is correct
41	Correct	6 ms	41252 KB	Output is correct
42	Correct	9 ms	41252 KB	Output is correct
43	Correct	13 ms	41252 KB	Output is correct
44	Correct	6 ms	41252 KB	Output is correct
45	Correct	13 ms	41252 KB	Output is correct
46	Correct	13 ms	41252 KB	Output is correct
47	Correct	13 ms	41252 KB	Output is correct
48	Correct	13 ms	41384 KB	Output is correct
49	Correct	896 ms	74336 KB	Output is correct
50	Correct	893 ms	77600 KB	Output is correct
51	Correct	889 ms	80408 KB	Output is correct
52	Correct	833 ms	72596 KB	Output is correct
53	Correct	706 ms	75616 KB	Output is correct
54	Correct	763 ms	78680 KB	Output is correct
55	Correct	713 ms	71128 KB	Output is correct
56	Correct	749 ms	74404 KB	Output is correct
57	Correct	816 ms	82184 KB	Output is correct
58	Correct	833 ms	78480 KB	Output is correct
59	Correct	816 ms	78420 KB	Output is correct
60	Correct	796 ms	76688 KB	Output is correct
61	Correct	483 ms	56696 KB	Output is correct
62	Correct	466 ms	56696 KB	Output is correct
63	Correct	1326 ms	70008 KB	Output is correct
64	Correct	1283 ms	64132 KB	Output is correct
65	Correct	1296 ms	60340 KB	Output is correct
66	Correct	1313 ms	58380 KB	Output is correct
67	Correct	1333 ms	57296 KB	Output is correct
68	Correct	1356 ms	56864 KB	Output is correct
69	Correct	1223 ms	56740 KB	Output is correct
70	Correct	1249 ms	56696 KB	Output is correct
71	Correct	1296 ms	56696 KB	Output is correct
72	Correct	1263 ms	56828 KB	Output is correct
73	Correct	1246 ms	56856 KB	Output is correct
74	Correct	1163 ms	56832 KB	Output is correct
75	Correct	1183 ms	56956 KB	Output is correct
76	Correct	1113 ms	57216 KB	Output is correct
77	Correct	913 ms	57732 KB	Output is correct
78	Correct	469 ms	58780 KB	Output is correct

답안 #35065

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