oj.uz

Submission #88018

# Submission time Handle Problem Language Result Execution time Memory
88018 2018-12-03T12:16:43 Z inom Hard route (IZhO17_road) C++14
19 / 100
 2000 ms 197316 KB 
#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 pb push_back
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define in freopen("road.in", "r", stdin);
#define out freopen("road.out", "w", stdout);

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;
*/
const int N = 5005;
const int INF = INT_MAX;
const int MOD = 998244353;

int TN = 1;

int n;
vector<int> leafs;
vector<int> verr[N];
int d[N][N], parent[N][N];

int get(int x, int y) {
    set<int> path; multiset<int> mpath;
    // printf("%d %d %d\n", x, y, parent[x][y]);
    // printf("cities between %d & %d are: ", x, y);
    while (parent[x][y] != 0) {
        path.insert(y); mpath.insert(y);
        y = parent[x][y];
    }
    path.insert(x); mpath.insert(x);
    if (sz(path) != sz(mpath)) {
        return -INF;
    }
    /*for (auto i: path) {
        printf("%d ", i);
    }
    puts("");*/
    int cur_ans = 0;
    for (int i = 1; i <= n; i++) {
        if (path.find(i) == path.end()) {
            // printf("%d ", i);
            int cur = INF;
            for (auto j: path) {
                // printf("%d %d ", j, d[i][j]);
                cur = min(cur, d[i][j]);
            }
            // puts("");
            cur_ans = max(cur_ans, cur);
        }
    }
    return cur_ans;
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        verr[x].pb(y); verr[y].pb(x);
    }
    for (int i = 1; i <= n; i++) {
        if (sz(verr[i]) == 1) {
            leafs.pb(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        queue<int> q; d[i][i] = 0; q.push(i); parent[i][i] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (auto to: verr[x]) {
                if (!d[i][to] && to != i) {
                    d[i][to] = d[i][x] + 1;
                    parent[i][to] = x; q.push(to);
                }
            }
        }
    }
    int ans = 0, cnt = 0;
    for (int i = 0; i < sz(leafs); i++) {
        for (int j = i + 1; j < sz(leafs); j++) {
            // puts("");
            int len = d[leafs[i]][leafs[j]], H = get(leafs[i], leafs[j]);
            // printf("%d %d %d %d \n", leafs[i], leafs[j], len, H);
            // puts("");
            len *= H;
            if (ans < len) {
                ans = len, cnt = 1;
            }
            else if (ans == len) {
                cnt++;
            }
        }
    }
    printf("%d %d", ans, cnt);
    return;
}

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

Compilation message

road.cpp: In function 'void solve()':
road.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
road.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 644 KB Output is correct
3 Correct 3 ms 756 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 5 ms 1756 KB Output is correct
8 Correct 5 ms 1756 KB Output is correct
9 Correct 6 ms 1764 KB Output is correct
10 Correct 5 ms 1764 KB Output is correct
11 Correct 17 ms 1764 KB Output is correct
12 Correct 21 ms 1776 KB Output is correct
13 Correct 22 ms 1776 KB Output is correct
14 Correct 20 ms 1776 KB Output is correct
15 Correct 2 ms 1776 KB Output is correct
16 Correct 4 ms 1776 KB Output is correct
17 Correct 4 ms 1776 KB Output is correct
18 Correct 4 ms 1776 KB Output is correct
19 Correct 3 ms 1776 KB Output is correct
20 Correct 3 ms 1776 KB Output is correct
21 Correct 3 ms 1776 KB Output is correct
22 Correct 3 ms 1836 KB Output is correct
23 Correct 4 ms 1836 KB Output is correct
24 Correct 13 ms 1860 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 644 KB Output is correct
3 Correct 3 ms 756 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 5 ms 1756 KB Output is correct
8 Correct 5 ms 1756 KB Output is correct
9 Correct 6 ms 1764 KB Output is correct
10 Correct 5 ms 1764 KB Output is correct
11 Correct 17 ms 1764 KB Output is correct
12 Correct 21 ms 1776 KB Output is correct
13 Correct 22 ms 1776 KB Output is correct
14 Correct 20 ms 1776 KB Output is correct
15 Correct 2 ms 1776 KB Output is correct
16 Correct 4 ms 1776 KB Output is correct
17 Correct 4 ms 1776 KB Output is correct
18 Correct 4 ms 1776 KB Output is correct
19 Correct 3 ms 1776 KB Output is correct
20 Correct 3 ms 1776 KB Output is correct
21 Correct 3 ms 1776 KB Output is correct
22 Correct 3 ms 1836 KB Output is correct
23 Correct 4 ms 1836 KB Output is correct
24 Correct 13 ms 1860 KB Output is correct
25 Execution timed out 2096 ms 197316 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 644 KB Output is correct
3 Correct 3 ms 756 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 5 ms 1756 KB Output is correct
8 Correct 5 ms 1756 KB Output is correct
9 Correct 6 ms 1764 KB Output is correct
10 Correct 5 ms 1764 KB Output is correct
11 Correct 17 ms 1764 KB Output is correct
12 Correct 21 ms 1776 KB Output is correct
13 Correct 22 ms 1776 KB Output is correct
14 Correct 20 ms 1776 KB Output is correct
15 Correct 2 ms 1776 KB Output is correct
16 Correct 4 ms 1776 KB Output is correct
17 Correct 4 ms 1776 KB Output is correct
18 Correct 4 ms 1776 KB Output is correct
19 Correct 3 ms 1776 KB Output is correct
20 Correct 3 ms 1776 KB Output is correct
21 Correct 3 ms 1776 KB Output is correct
22 Correct 3 ms 1836 KB Output is correct
23 Correct 4 ms 1836 KB Output is correct
24 Correct 13 ms 1860 KB Output is correct
25 Execution timed out 2096 ms 197316 KB Time limit exceeded
26 Halted 0 ms 0 KB -