oj.uz

Submission #88019

# Submission time Handle Problem Language Result Execution time Memory
88019 2018-12-03T12:22:46 Z inom Hard route (IZhO17_road) C++14
19 / 100
 2000 ms 196964 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:22:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
road.cpp: In function 'void solve()':
road.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
road.cpp:73: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 2 ms 504 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 3 ms 752 KB Output is correct
7 Correct 5 ms 1524 KB Output is correct
8 Correct 5 ms 1524 KB Output is correct
9 Correct 6 ms 1568 KB Output is correct
10 Correct 5 ms 1568 KB Output is correct
11 Correct 23 ms 1568 KB Output is correct
12 Correct 20 ms 1588 KB Output is correct
13 Correct 19 ms 1612 KB Output is correct
14 Correct 20 ms 1612 KB Output is correct
15 Correct 4 ms 1612 KB Output is correct
16 Correct 4 ms 1612 KB Output is correct
17 Correct 4 ms 1612 KB Output is correct
18 Correct 3 ms 1612 KB Output is correct
19 Correct 3 ms 1648 KB Output is correct
20 Correct 3 ms 1648 KB Output is correct
21 Correct 3 ms 1648 KB Output is correct
22 Correct 3 ms 1648 KB Output is correct
23 Correct 4 ms 1648 KB Output is correct
24 Correct 13 ms 1660 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 2 ms 504 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 3 ms 752 KB Output is correct
7 Correct 5 ms 1524 KB Output is correct
8 Correct 5 ms 1524 KB Output is correct
9 Correct 6 ms 1568 KB Output is correct
10 Correct 5 ms 1568 KB Output is correct
11 Correct 23 ms 1568 KB Output is correct
12 Correct 20 ms 1588 KB Output is correct
13 Correct 19 ms 1612 KB Output is correct
14 Correct 20 ms 1612 KB Output is correct
15 Correct 4 ms 1612 KB Output is correct
16 Correct 4 ms 1612 KB Output is correct
17 Correct 4 ms 1612 KB Output is correct
18 Correct 3 ms 1612 KB Output is correct
19 Correct 3 ms 1648 KB Output is correct
20 Correct 3 ms 1648 KB Output is correct
21 Correct 3 ms 1648 KB Output is correct
22 Correct 3 ms 1648 KB Output is correct
23 Correct 4 ms 1648 KB Output is correct
24 Correct 13 ms 1660 KB Output is correct
25 Execution timed out 2112 ms 196964 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 2 ms 504 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 3 ms 752 KB Output is correct
7 Correct 5 ms 1524 KB Output is correct
8 Correct 5 ms 1524 KB Output is correct
9 Correct 6 ms 1568 KB Output is correct
10 Correct 5 ms 1568 KB Output is correct
11 Correct 23 ms 1568 KB Output is correct
12 Correct 20 ms 1588 KB Output is correct
13 Correct 19 ms 1612 KB Output is correct
14 Correct 20 ms 1612 KB Output is correct
15 Correct 4 ms 1612 KB Output is correct
16 Correct 4 ms 1612 KB Output is correct
17 Correct 4 ms 1612 KB Output is correct
18 Correct 3 ms 1612 KB Output is correct
19 Correct 3 ms 1648 KB Output is correct
20 Correct 3 ms 1648 KB Output is correct
21 Correct 3 ms 1648 KB Output is correct
22 Correct 3 ms 1648 KB Output is correct
23 Correct 4 ms 1648 KB Output is correct
24 Correct 13 ms 1660 KB Output is correct
25 Execution timed out 2112 ms 196964 KB Time limit exceeded
26 Halted 0 ms 0 KB -