Submission #93166

#	Time	Username	Problem	Language	Result	Execution time	Memory
93166		inom	Hard route (IZhO17_road)	C++14	52 / 100	537 ms	5112 KiB

road

#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define fi first
#define se second
#define new new228
#define pb push_back
#define rank rank228
#define int long long
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
 
using namespace std;
using namespace __gnu_pbds;
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma warning(disable : 4996)
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // st.oreder_of_key();

const int N = 100100;
const int INF = 1e15 + 7;
const int MAXN = 4 * N;
const int MOD = 998244353;
 
int TN = 1;

int n;
int ans, cnt;
int dp[N], dp2[N];
vector<int> verr[N];

void init(int x, int pr = -1) {
    dp[x] = dp2[x] = 0;
    for (int to: verr[x]) {
        if (to == pr) continue;
        init(to, x);
        if (dp[x] < dp[to] + 1) {
            dp2[x] = dp[x];
            dp[x] = dp[to] + 1;
        } 
        else if (dp2[x] < dp[to] + 1) {
            dp2[x] = dp[to] + 1;
        }
        // printf("%lld dp[%lld] = %lld, dp2[%lld] = %lld\n", x, x, dp[x], x, dp2[x]);
    }
}

void dfs(int x, int pr = -1, int len = 0, int mx = 0) {
    if (sz(verr[x]) == 1 && pr != -1) {
        if (ans < len * mx) {
            ans = len * mx; cnt = 1;
        } else {
            cnt += (ans == len * mx) ;
        }
        return;
    }
    for (auto to: verr[x]) {
        if (to == pr) continue;
        if (dp[to] + 1 == dp[x]) {
            dfs(to, x, len + 1, max(dp2[x], mx));
        } else {
            dfs(to, x, len + 1, max(dp[x], mx));
        }
    }
}

void solve() {
    scanf("%lld", &n);
    for (int i = 1; i < n; i++) {
        int x, y; scanf("%lld %lld", &x, &y);
        verr[x].pb(y); verr[y].pb(x);
    }
    for (int i = 1; i <= n; i++) {
        if (sz(verr[i]) == 1) {
            // printf("\nWe are in %lld, the ways are\n", i);
            init(i, -1); dfs(i);
            /*for (int j = 1; j <= n; j++) {
                printf("%lld dp[%lld] = %lld, dp2[%lld] = %lld\n", j, j, dp[j], j, dp2[j]);
            }
            puts("");*/
        }
    }
    printf("%lld %lld", ans, cnt / 2);
    return;
}

signed main() {
    // in; out; // cin >> TN;
    while (TN--) { solve(); }
    return 0;
}

Compilation message (stderr)

road.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
road.cpp: In function 'void solve()':
road.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
road.cpp:77:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%lld %lld", &x, &y);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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