제출 #173088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173088		VEGAnn	Hard route (IZhO17_road)	C++14	52 / 100	404 ms	1144 KiB

road

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define PB push_back
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5100;
const int oo = 2e9;
vector<int> g[N];
int n, ans = -1, kol = 0, mx[N];

void build_sz(int v, int p){
    mx[v] = 0;
    for (int u : g[v]){
        if (u == p) continue;
        build_sz(u, v);
        mx[v] = max(mx[v], mx[u] + 1);
    }
}

void dfs(int v, int p, int len, int cmax){

    if (sz(g[v]) == 1 && p >= 0){
        int clen = len * cmax;

        if (ans < clen){
            ans = clen;
            kol = 0;
        }

        if (ans == clen)
            kol++;

        return;
    }

    int mx1 = -1, mx2 = -1, n1 = -1, n2 = -1;

    for (int u : g[v]){
        if (u == p) continue;
        if (mx1 < mx[u] + 1){
            swap(mx1, mx2);
            swap(n1, n2);
            mx1 = mx[u] + 1;
            n1 = u;
        } else if (mx2 < mx[u] + 1){
            mx2 = mx[u] + 1;
            n2 = u;
        }
    }

    for (int u : g[v]){
        if (u == p) continue;
        if (n1 == u)
            dfs(u, v, len + 1, max(cmax, mx2));
        else dfs(u, v, len + 1, max(cmax, mx1));
    }

}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

  cin >> n;
    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].PB(y);
        g[y].PB(x);
    }

    for (int i = 0; i < n; i++)
        if (sz(g[i]) == 1){
            build_sz(i, -1);
            dfs(i, -1, 0, 0);
        }

    cout << ans << " " << (kol >> 1);

    return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 0 / 48