oj.uz

Submission #1075681

# Submission time Handle Problem Language Result Execution time Memory
1075681 2024-08-26T08:32:44 Z shmax Dreaming (IOI13_dreaming) C++17
18 / 100
 36 ms 18388 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;
    };
    vec<int> diams;
    auto build = [&](int v) {
        if (used[v]) return;
        Val cur = dfs(v, -1);
        diams.push_back(cur.max_diam);
        if (cur.d_u == cur.d_v) {
            diam.push_back(cur.max_diam);
            return;
        }
        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;
        int best = 1e9;
        for (int i = 0; i < edges.size(); i++) {
            best = min(best, max(cur_sum, sum - cur_sum));
            cur_sum += edges[i];
        }
        diam.push_back(best);

//        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 diams[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:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         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 36 ms 18388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 36 ms 18388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6100 KB Output is correct
2 Correct 22 ms 6160 KB Output is correct
3 Correct 15 ms 6104 KB Output is correct
4 Correct 18 ms 6088 KB Output is correct
5 Correct 17 ms 5848 KB Output is correct
6 Correct 18 ms 6616 KB Output is correct
7 Correct 17 ms 6356 KB Output is correct
8 Correct 19 ms 5848 KB Output is correct
9 Correct 15 ms 5848 KB Output is correct
10 Correct 18 ms 6316 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 3720 KB Output is correct
13 Correct 4 ms 3800 KB Output is correct
14 Correct 4 ms 3752 KB Output is correct
15 Correct 4 ms 3720 KB Output is correct
16 Correct 4 ms 3720 KB Output is correct
17 Correct 4 ms 3720 KB Output is correct
18 Correct 7 ms 3800 KB Output is correct
19 Correct 4 ms 3752 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 4 ms 3640 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 36 ms 18388 KB Output isn't correct
2 Halted 0 ms 0 KB -