oj.uz

Submission #1075658

# Submission time Handle Problem Language Result Execution time Memory
1075658 2024-08-26T08:23:33 Z shmax Dreaming (IOI13_dreaming) C++17
0 / 100
 39 ms 18296 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

template<typename T>
using vec = vector<T>;

int travelTime(int n, int M, int L, int A[], int B[], int T[]) {
    vec<vec<pair<int, int>>> g(n);
    for (int i = 0; i < M; i++) {
        g[A[i]].emplace_back(B[i], T[i]);
        g[B[i]].emplace_back(A[i], T[i]);
    }
    vec<bool> used(n);
    vec<int> diam;
    struct Val {
        int max_diam;
        int d_v;
        int d_u;
        int max_depth;
        int v_depth;
    };
    function<Val(int, int)> dfs = [&](int v, int p) -> Val {
        used[v] = true;
        Val cur = {0, v, v, 0, v};
        int t1 = 0, t2 = 0;
        int v1 = v, v2 = v;
        for (auto [u, w]: g[v]) {
            if (u == p) continue;
            Val nxt = dfs(u, v);
            if (cur.max_depth < nxt.max_depth + w) {
                cur.max_depth = nxt.max_depth + w;
                cur.v_depth = nxt.v_depth;
            }
            if (t1 < nxt.max_depth + w) {
                t2 = t1;
                v2 = v1;
                t1 = nxt.max_depth + w;
                v1 = nxt.v_depth;
            } else if (t2 < nxt.max_depth + w) {
                t2 = nxt.max_depth + w;
                v2 = nxt.v_depth;
            }
            if (cur.max_diam < nxt.max_diam) {
                cur.max_diam = nxt.max_diam;
                cur.d_v = nxt.d_v;
                cur.d_u = nxt.d_u;
            }
        }
        if (cur.max_diam < t1 + t2) {
            cur.max_diam = t1 + t2;
            cur.d_v = v1;
            cur.d_u = v2;
        }
        return cur;
    };

    auto build = [&](int v) {
        if (used[v]) return;
        Val cur = dfs(v, -1);
        vec<int> edges;
        function<bool(int, int)> dfs1 = [&](int v, int p) {
            if (v == cur.d_u) return true;
            for (auto [u, w]: g[v]) {
                if (u == p) continue;
                if (dfs1(u, v)) {
                    edges.push_back(w);
                    return true;
                }
            }
            return false;
        };
        dfs1(cur.d_v, -1);
        int sum = accumulate(edges.begin(), edges.end(), 0);
        int cur_sum = 0;

        for (int i = 0; i < edges.size(); i++) {
            if ((cur_sum + edges[i]) * 2 >= sum) {
                int var1 = sum - cur_sum;
                int var2 = cur_sum + edges[i];
                diam.push_back(min(var1, var2));
                return;
            } else {
                cur_sum += edges[i];
            }
        }

    };

    for (int i = 0; i < n; i++)
        build(i);

    sort(diam.rbegin(), diam.rend());
    if (diam.size() == 1) {
        return diam[0];
    }
    if (diam.size() == 2) {
        return diam[0] + diam[1] + L;
    }
    if (diam.size() >= 3) {
        return max(diam[0] + diam[1] + L, diam[1] + diam[2] + 2 * L);
    }

}

Compilation message

dreaming.cpp: In lambda function:
dreaming.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int i = 0; i < edges.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:10:33: warning: control reaches end of non-void function [-Wreturn-type]
   10 |     vec<vec<pair<int, int>>> g(n);
      |                                 ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 18296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 18296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5468 KB Output is correct
2 Correct 25 ms 5552 KB Output is correct
3 Correct 16 ms 5468 KB Output is correct
4 Correct 16 ms 5464 KB Output is correct
5 Correct 16 ms 5468 KB Output is correct
6 Correct 19 ms 5980 KB Output is correct
7 Correct 17 ms 5724 KB Output is correct
8 Correct 15 ms 5360 KB Output is correct
9 Correct 16 ms 5464 KB Output is correct
10 Correct 17 ms 5724 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 4 ms 2652 KB Output is correct
13 Correct 4 ms 2652 KB Output is correct
14 Correct 5 ms 2648 KB Output is correct
15 Correct 4 ms 2652 KB Output is correct
16 Correct 5 ms 2652 KB Output is correct
17 Correct 6 ms 2648 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 4 ms 2652 KB Output is correct
20 Runtime error 1 ms 348 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 18296 KB Output isn't correct
2 Halted 0 ms 0 KB -