답안 #38703 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38703	2018-01-06T09:25:55 Z	grumpy_gordon	Hard route (IZhO17_road)	C++14	19 / 100	2000 ms	40192 KB

road

/*
                     .:*+=%@@@@@@=-.
                 .:=@#@@@#@@#######%==*.
              .-=####@######%*-.....:%##%.
            .*@###########%+:--........-%@-
          .*@##############@+--.........-:%-
        .+##################@==%%%%=+*:----+.
      .-@####################%++%@@@@@=+**%@@*
      .%###################@%%@@@###@%+:--%@@%.
     -@###################@%%%%*::*%++:-----=@+.
    -#####################@%=++++++*:-------.-=:
   .+####################@%++*::-:::--::*:::***=:
   .@#####################%=++*::::-:::++*=##@@#@-
  ..#####################@%%=++**:::::**+%@#@%%##-..
   .%####################@@%=+++*+****::*=@######@.
  .=######################@%%==+==++**+=@%@##@###+:...
  -#######################@@@%%%===++=@@@%=++===*::--...
  -########################@@@@@@@%==%%=++==@@:::::*:--.
..:#########################@@@@@@%%======++++::-..:-.--...
%#############################@###@%%@@%==%=%*----.--.::---.
#############################################*-:*:-:---*---- .
#############################################*--*--:---*---:-.
#############################################+--::--::-*::-::.
###########################################+:*-.---.---.:---*-..
###########################################**:-----------------.
##########################################@::**:--::::::--:::::-
###########################################:--:*:::::::::**::*+*
###########################################=:::***::::::**:::*+*
############################@@@@@@#########@+****::::********+++
############################@%%%%%@@@@@@@###%+***::::::::***+==+
############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
#############################@%%%%%%%%%%@#####=::--------:*=%@%+
%###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
----------------------------------------------
--------------------------------------------
----------------------------------------------
--------------------------------------------
----------------------------------------------

         o###########oo
      o##"          ""##o
    o#"                "##
  o#"                    "#o
 #"  ##              ##   "##
#"                          ##
#  ###################       #
#                            #
#                            #
#                            #
#                            #
#                            #
#                            #
#o                           #
"#o                         ##
 "#o                       ##
  "#o                    o#"
   "#o                  ##
     "#o              o#"
       "#ooo      ooo#######oo
        ###############   "######o
     o###""        "###o      # ###
   o###o     oooo    ###    oo####"
 o###**#     #**#   ############"
 ""##""""""""""###########    #
    # oooooooo#"#**     ##    #
    # #       # # **    ##    #
    #o#       #o#  *****###ooo#
                        ##
                        ##   o###o
                        ## o##***##
               o########## #***#**##o
             o##"   ""###  #***##***#
 o#######o  ###   oo####   ##**####*#
o##"  ""#############""     ##****###
##"         ##              ##*##*###
##          ###              ##### ##
##           ###              # ##  #
##            ##                 #
##             ##
##             ###
##              ###oo
###              ""###
 ###
  ###
*/
#include <bits/stdc++.h>

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

int mysqrt(ll x){
    int l = 0, r = 1e9 + 1;
    while (r - l > 1){
        int m = (l + r) / 2;
        if (m * (ll)m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}

mt19937 rnd(1337);

ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;

ll myrand(){
    ll ZR = (XR * AR + YR * BR + CR) % MODR;
    XR = YR;
    YR = ZR;
    return ZR;
}

const int Mod = 1e9 + 7;

int bpow(int x, int y){
    if (y == 0)
        return 1;
    if (y == 1)
        return x;
    int ret = bpow(x, y >> 1);
    ret = (ret * (ll)ret) % Mod;
    if (y & 1)
        ret = (ret * (ll)x) % Mod;
    return ret;
}

int bdiv(int x, int y){
    return (x * (ll)bpow(y, Mod - 2)) % Mod;
}

void setmin(int &x, int y){
    x = min(x, y);
}

void setmax(int &x, int y){
    x = max(x, y);
}

const ll llinf = 1e18 + 100;

const int maxn = 5e5 + 100, maxw = 1e6 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17;

int n;

vector<int> e[maxn];

vector<int> q[maxn];

vector<int> g[maxn];

ll ans, answer = 1;

void upd(ll x, ll y){
    if (ans > x)
        return;
    if (ans < x)
        ans = x, answer = 0;
    answer += y;
}

int dfs0(int v, int par){
    int ret = 0;
    q[v].resize(e[v].size());
    g[v].resize(e[v].size());
    for (int i = 0; i < e[v].size(); i++)
    if (e[v][i] != par){
        q[v][i] = dfs0(e[v][i], v) + 1;
        ret = max(ret, q[v][i]);
    }
    return ret;
}

void dfs(int v, int par, int pv){
    int a = 0, b = 0, c = 0, x = 0, y = 0, z = 0;
    if (pv)
        a = pv, x = 1;
    for (int i = 0; i < e[v].size(); i++)
    if (e[v][i] != par){
        if (a < q[v][i])
            c = b, b = a, a = q[v][i], z = y, y = x, x = 1;
        else
        if (a == q[v][i])
            x++;
        else
        if (b < q[v][i])
            c = b, b = q[v][i], z = y, y = 1;
        else
        if (b == q[v][i])
            y++;
        else
        if (c < q[v][i])
            c = q[v][i], z = 1;
        else
        if (c == q[v][i])
            z++;
    }
    if (x + y + z > 2){
        if (x == 1)
            if (y == 1)
                upd(a * (ll)(b + c), z);
            else
                upd(a * (ll)2 * b, y * (ll)(y - 1) / 2);
        else
        if (x > 2)
            upd(a * (ll)2 * a, x * (ll)(x - 1) / 2);
        else
            upd(a * (ll)(a + b), 2 * y);
    }
    g[v][0] = q[v][0];
    for (int i = 1; i < q[v].size(); i++)
        g[v][i] = max(q[v][i], g[v][i - 1]);
    a = pv;
    for (int i = q[v].size() - 1; i >= 0; i--)
    if (e[v][i] != par){
        dfs(e[v][i], v, max(a, (i ? g[v][i - 1] : 0)) + 1);
        a = max(a, q[v][i]);
    }
}

int dist, dans;

void getfar(int v, int par, int ds){
    if (ds > dist)
        dist = ds, dans = v;
    for (auto i : e[v])
    if (i != par)
        getfar(i, v, ds + 1);
}

ll X, Y = 1;

bool vis[maxn];

int pt[maxn];

int getf(int v, int par){
    int ret = 0;
    for (auto i : e[v])
    if (i != par)
        ret = max(ret, getf(i, v) + 1);
    return ret;
}

void go(int v, int par, int len){
    pt[len] = v;
    if (len && e[v].size() == 1){
        for (int i = 0; i < n; i++)
            vis[i] = 0;
        for (int i = 0; i <= len; i++)
            vis[pt[i]] = 1;
        int z = 0;
        for (int i = 0; i <= len; i++){
            int u = pt[i];
            for (auto j : e[u])
            if (!vis[j])
                z = max(z, getf(j, u) + 1);
        }
        if (X < z * len)
            X = z * len, Y = 1;
        else
        if (X == z * len)
            Y++;
        return;
    }
    for (auto i : e[v])
    if (i != par)
        go(i, v, len + 1);
}

int main()
{
    #ifdef ONPC
    //ifstream cin("a.in");
    //ofstream cout("a.out");
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #else
    //ifstream cin("road.in");
    //ofstream cout("road.out");
    //freopen("money.in", "r", stdin);
    //freopen("money.out", "w", stdout);
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++){
        int v, u;
        cin >> v >> u;
        v--;
        u--;
        e[v].push_back(u);
        e[u].push_back(v);
    }
    dfs0(0, -1);
    dfs(0, -1, 0);
    for (int i = 0; i < n; i++)
    if (e[i].size() == 1)
        go(i, -1, 0);
    Y /= 2;
    assert(ans == X);
    //assert(Y >= answer);
    cout << X << ' ' << Y;
    //cout << ans << ' ' << answer;
}

Compilation message

road.cpp: In function 'int dfs0(int, int)':
road.cpp:177:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < e[v].size(); i++)
                       ^
road.cpp: In function 'void dfs(int, int, int)':
road.cpp:189:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < e[v].size(); i++)
                       ^
road.cpp:222:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < q[v].size(); i++)
                       ^

Subtask #1
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	39788 KB	Output is correct
2	Correct	9 ms	39788 KB	Output is correct
3	Correct	6 ms	39788 KB	Output is correct
4	Correct	9 ms	39788 KB	Output is correct
5	Correct	3 ms	39788 KB	Output is correct
6	Correct	13 ms	39788 KB	Output is correct
7	Correct	13 ms	39788 KB	Output is correct
8	Correct	16 ms	39788 KB	Output is correct
9	Correct	13 ms	39788 KB	Output is correct
10	Correct	6 ms	39788 KB	Output is correct
11	Correct	13 ms	39788 KB	Output is correct
12	Correct	9 ms	39788 KB	Output is correct
13	Correct	9 ms	39788 KB	Output is correct
14	Correct	16 ms	39788 KB	Output is correct
15	Correct	9 ms	39788 KB	Output is correct
16	Correct	6 ms	39788 KB	Output is correct
17	Correct	9 ms	39788 KB	Output is correct
18	Correct	19 ms	39788 KB	Output is correct
19	Correct	13 ms	39788 KB	Output is correct
20	Correct	13 ms	39788 KB	Output is correct
21	Correct	9 ms	39788 KB	Output is correct
22	Correct	9 ms	39788 KB	Output is correct
23	Correct	16 ms	39788 KB	Output is correct
24	Correct	16 ms	39788 KB	Output is correct

Subtask #2
0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	39788 KB	Output is correct
2	Correct	9 ms	39788 KB	Output is correct
3	Correct	6 ms	39788 KB	Output is correct
4	Correct	9 ms	39788 KB	Output is correct
5	Correct	3 ms	39788 KB	Output is correct
6	Correct	13 ms	39788 KB	Output is correct
7	Correct	13 ms	39788 KB	Output is correct
8	Correct	16 ms	39788 KB	Output is correct
9	Correct	13 ms	39788 KB	Output is correct
10	Correct	6 ms	39788 KB	Output is correct
11	Correct	13 ms	39788 KB	Output is correct
12	Correct	9 ms	39788 KB	Output is correct
13	Correct	9 ms	39788 KB	Output is correct
14	Correct	16 ms	39788 KB	Output is correct
15	Correct	9 ms	39788 KB	Output is correct
16	Correct	6 ms	39788 KB	Output is correct
17	Correct	9 ms	39788 KB	Output is correct
18	Correct	19 ms	39788 KB	Output is correct
19	Correct	13 ms	39788 KB	Output is correct
20	Correct	13 ms	39788 KB	Output is correct
21	Correct	9 ms	39788 KB	Output is correct
22	Correct	9 ms	39788 KB	Output is correct
23	Correct	16 ms	39788 KB	Output is correct
24	Correct	16 ms	39788 KB	Output is correct
25	Execution timed out	2000 ms	40192 KB	Execution timed out
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	39788 KB	Output is correct
2	Correct	9 ms	39788 KB	Output is correct
3	Correct	6 ms	39788 KB	Output is correct
4	Correct	9 ms	39788 KB	Output is correct
5	Correct	3 ms	39788 KB	Output is correct
6	Correct	13 ms	39788 KB	Output is correct
7	Correct	13 ms	39788 KB	Output is correct
8	Correct	16 ms	39788 KB	Output is correct
9	Correct	13 ms	39788 KB	Output is correct
10	Correct	6 ms	39788 KB	Output is correct
11	Correct	13 ms	39788 KB	Output is correct
12	Correct	9 ms	39788 KB	Output is correct
13	Correct	9 ms	39788 KB	Output is correct
14	Correct	16 ms	39788 KB	Output is correct
15	Correct	9 ms	39788 KB	Output is correct
16	Correct	6 ms	39788 KB	Output is correct
17	Correct	9 ms	39788 KB	Output is correct
18	Correct	19 ms	39788 KB	Output is correct
19	Correct	13 ms	39788 KB	Output is correct
20	Correct	13 ms	39788 KB	Output is correct
21	Correct	9 ms	39788 KB	Output is correct
22	Correct	9 ms	39788 KB	Output is correct
23	Correct	16 ms	39788 KB	Output is correct
24	Correct	16 ms	39788 KB	Output is correct
25	Execution timed out	2000 ms	40192 KB	Execution timed out
26	Halted	0 ms	0 KB	-

답안 #38703

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 0 / 33.0

Subtask #3 0 / 48.0

Subtask #1
19.0 / 19.0

Subtask #2
0 / 33.0

Subtask #3
0 / 48.0