oj.uz

Submission #456398

# Submission time Handle Problem Language Result Execution time Memory
456398 2021-08-06T16:16:37 Z dxz05 Hard route (IZhO17_road) C++14
52 / 100
 2000 ms 78848 KB 
#pragma GCC optimize("Ofast,O2,O3")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 2e6 + 3e2;
const int M = 5055;

vector<pair<int, int>> g[N];

void dfs(int v, int p, int d, int &mx){
    mx = max(mx, d);
    for (auto edge : g[v]){
        int u = edge.second;
        if (u != p) dfs(u, v, d + 1, mx);
    }
}

int get(int v, int a, int b){
    int sz = g[v].size();
    for (int i = sz - 1; i >= 0; i--){
        if (g[v][i].second != a && g[v][i].second != b) return g[v][i].first;
    }
    return 0;
}

int ans = -1, cnt = 0;
void dfs2(int v, int p, int d, int h){
    int sz = g[v].size();
    if (sz == 1){
        int cost = d * h;
        if (cost > ans){
            ans = cost;
            cnt = 1;
        } else if (cost == ans) cnt++;
        debug(v, cost, d, h);
        return;
    }

    for (auto edge : g[v]){
        int u = edge.second, hh = get(v, u, p);
        if (u != p) dfs2(u, v, d + 1, max(h, hh));
    }
}

void solve(int TC) {
    int n;
    cin >> n;

    if (n == 2){
        cout << 0 << ' ' << 1 << endl;
        return;
    }

    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(0, v);
        g[v].emplace_back(0, u);
    }

    for (int i = 1; i <= n; i++){
        for (auto &edge : g[i]){
            dfs(edge.second, i, 1, edge.first);
        }
        sort(all(g[i]));
    }

    for (int i = 1; i <= n; i++){
        if (g[i].size() == 1){
            debug(i);
            dfs2(g[i][0].second, i, 1, 0);
        }
    }

    assert(cnt % 2 == 0);

    cout << ans << ' ' << cnt / 2 << endl;

}

int main() {
    startTime = clock();
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Compilation message

road.cpp: In function 'void dfs2(int, int, int, int)':
road.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
road.cpp:70:9: note: in expansion of macro 'debug'
   70 |         debug(v, cost, d, h);
      |         ^~~~~
road.cpp: In function 'void solve(int)':
road.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
road.cpp:105:13: note: in expansion of macro 'debug'
  105 |             debug(i);
      |             ^~~~~
road.cpp: In function 'int main()':
road.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
road.cpp:133:9: note: in expansion of macro 'debug'
  133 |         debug(test);
      |         ^~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 29 ms 47260 KB Output is correct
3 Correct 29 ms 47180 KB Output is correct
4 Correct 29 ms 47168 KB Output is correct
5 Correct 29 ms 47288 KB Output is correct
6 Correct 29 ms 47180 KB Output is correct
7 Correct 31 ms 47300 KB Output is correct
8 Correct 29 ms 47180 KB Output is correct
9 Correct 28 ms 47200 KB Output is correct
10 Correct 28 ms 47292 KB Output is correct
11 Correct 29 ms 47292 KB Output is correct
12 Correct 29 ms 47184 KB Output is correct
13 Correct 29 ms 47244 KB Output is correct
14 Correct 28 ms 47188 KB Output is correct
15 Correct 29 ms 47180 KB Output is correct
16 Correct 28 ms 47228 KB Output is correct
17 Correct 29 ms 47268 KB Output is correct
18 Correct 29 ms 47188 KB Output is correct
19 Correct 31 ms 47180 KB Output is correct
20 Correct 29 ms 47188 KB Output is correct
21 Correct 28 ms 47236 KB Output is correct
22 Correct 28 ms 47236 KB Output is correct
23 Correct 30 ms 47180 KB Output is correct
24 Correct 29 ms 47172 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 29 ms 47260 KB Output is correct
3 Correct 29 ms 47180 KB Output is correct
4 Correct 29 ms 47168 KB Output is correct
5 Correct 29 ms 47288 KB Output is correct
6 Correct 29 ms 47180 KB Output is correct
7 Correct 31 ms 47300 KB Output is correct
8 Correct 29 ms 47180 KB Output is correct
9 Correct 28 ms 47200 KB Output is correct
10 Correct 28 ms 47292 KB Output is correct
11 Correct 29 ms 47292 KB Output is correct
12 Correct 29 ms 47184 KB Output is correct
13 Correct 29 ms 47244 KB Output is correct
14 Correct 28 ms 47188 KB Output is correct
15 Correct 29 ms 47180 KB Output is correct
16 Correct 28 ms 47228 KB Output is correct
17 Correct 29 ms 47268 KB Output is correct
18 Correct 29 ms 47188 KB Output is correct
19 Correct 31 ms 47180 KB Output is correct
20 Correct 29 ms 47188 KB Output is correct
21 Correct 28 ms 47236 KB Output is correct
22 Correct 28 ms 47236 KB Output is correct
23 Correct 30 ms 47180 KB Output is correct
24 Correct 29 ms 47172 KB Output is correct
25 Correct 660 ms 47696 KB Output is correct
26 Correct 628 ms 47684 KB Output is correct
27 Correct 610 ms 47692 KB Output is correct
28 Correct 655 ms 47696 KB Output is correct
29 Correct 536 ms 47720 KB Output is correct
30 Correct 517 ms 47712 KB Output is correct
31 Correct 515 ms 47808 KB Output is correct
32 Correct 519 ms 47708 KB Output is correct
33 Correct 500 ms 47812 KB Output is correct
34 Correct 531 ms 47780 KB Output is correct
35 Correct 498 ms 47712 KB Output is correct
36 Correct 490 ms 47716 KB Output is correct
37 Correct 629 ms 47748 KB Output is correct
38 Correct 622 ms 47752 KB Output is correct
39 Correct 610 ms 47544 KB Output is correct
40 Correct 632 ms 47700 KB Output is correct
41 Correct 617 ms 47488 KB Output is correct
42 Correct 615 ms 47556 KB Output is correct
43 Correct 596 ms 47480 KB Output is correct
44 Correct 576 ms 47484 KB Output is correct
45 Correct 466 ms 47468 KB Output is correct
46 Correct 337 ms 47448 KB Output is correct
47 Correct 431 ms 47504 KB Output is correct
48 Correct 323 ms 47536 KB Output is correct

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 29 ms 47260 KB Output is correct
3 Correct 29 ms 47180 KB Output is correct
4 Correct 29 ms 47168 KB Output is correct
5 Correct 29 ms 47288 KB Output is correct
6 Correct 29 ms 47180 KB Output is correct
7 Correct 31 ms 47300 KB Output is correct
8 Correct 29 ms 47180 KB Output is correct
9 Correct 28 ms 47200 KB Output is correct
10 Correct 28 ms 47292 KB Output is correct
11 Correct 29 ms 47292 KB Output is correct
12 Correct 29 ms 47184 KB Output is correct
13 Correct 29 ms 47244 KB Output is correct
14 Correct 28 ms 47188 KB Output is correct
15 Correct 29 ms 47180 KB Output is correct
16 Correct 28 ms 47228 KB Output is correct
17 Correct 29 ms 47268 KB Output is correct
18 Correct 29 ms 47188 KB Output is correct
19 Correct 31 ms 47180 KB Output is correct
20 Correct 29 ms 47188 KB Output is correct
21 Correct 28 ms 47236 KB Output is correct
22 Correct 28 ms 47236 KB Output is correct
23 Correct 30 ms 47180 KB Output is correct
24 Correct 29 ms 47172 KB Output is correct
25 Correct 660 ms 47696 KB Output is correct
26 Correct 628 ms 47684 KB Output is correct
27 Correct 610 ms 47692 KB Output is correct
28 Correct 655 ms 47696 KB Output is correct
29 Correct 536 ms 47720 KB Output is correct
30 Correct 517 ms 47712 KB Output is correct
31 Correct 515 ms 47808 KB Output is correct
32 Correct 519 ms 47708 KB Output is correct
33 Correct 500 ms 47812 KB Output is correct
34 Correct 531 ms 47780 KB Output is correct
35 Correct 498 ms 47712 KB Output is correct
36 Correct 490 ms 47716 KB Output is correct
37 Correct 629 ms 47748 KB Output is correct
38 Correct 622 ms 47752 KB Output is correct
39 Correct 610 ms 47544 KB Output is correct
40 Correct 632 ms 47700 KB Output is correct
41 Correct 617 ms 47488 KB Output is correct
42 Correct 615 ms 47556 KB Output is correct
43 Correct 596 ms 47480 KB Output is correct
44 Correct 576 ms 47484 KB Output is correct
45 Correct 466 ms 47468 KB Output is correct
46 Correct 337 ms 47448 KB Output is correct
47 Correct 431 ms 47504 KB Output is correct
48 Correct 323 ms 47536 KB Output is correct
49 Execution timed out 2067 ms 78848 KB Time limit exceeded
50 Halted 0 ms 0 KB -