oj.uz

Submission #880594

# Submission time Handle Problem Language Result Execution time Memory
880594 2023-11-29T17:14:42 Z Mr_Husanboy Dreaming (IOI13_dreaming) C++17
0 / 100
 31 ms 12508 KB 
    #include "dreaming.h"
    #include <bits/stdc++.h>

    using namespace std;
    using ll = long long;
    const ll infl = 1e18;
    template<typename T>
    int len(T &a){
        return a.size();
    }


    int travelTime(int n, int m, int L, int a[], int b[], int t[]) {
        vector<vector<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]);
        }


        vector<ll> disa(n);
        vector<bool> vis(n);
        int mx = 0;

        auto dfs = [&](auto &dfs, int i, int p = -1)->void{
            vis[i] = 1;
            for(auto [u, w] : g[i]){
                if(u == p) continue;
                disa[u] = disa[i] + w;
                dfs(dfs, u, i);
            }
            if(disa[mx] < disa[i]) mx = i;
        };
        ll mxx = infl;

        auto dfs2 = [&](auto &dfs2, int i, int p = -1, ll d = 0)->void{
            vis[i] = 1;
            mxx = min(mxx, max(d, disa[i]));
            for(auto [u, w] : g[i]){
                if(u == p) continue;
                dfs2(dfs2, u, i, d + w);
            }
        };
        ll ans = 0;
        vector<ll> dis;
        for(int i = 0; i < n; i ++){
            if(vis[i]) continue;
            mx = i;
            mxx = infl;
            dfs(dfs, i);
            disa[mx] = 0;
            dfs(dfs, mx);
            ans = max(ans, disa[mx]);
            dfs2(dfs2, mx);
            dis.push_back(mxx);
        }
        assert(m == n - 2);
        if(len(dis) == 1){
            return max(ans, dis[0]);
        }
        if(len(dis) == 2){
            return max(ans, dis[0] + dis[2] + L);
        }
        sort(dis.begin(), dis.end());
        n = dis.size();
        ans = max({ans, dis[n - 1] + dis[n - 2] + L, dis[n - 2] + dis[n - 3] + 2 * L});
        return ans;
    }

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10096 KB Output is correct
2 Correct 31 ms 10088 KB Output is correct
3 Correct 21 ms 6748 KB Output is correct
4 Correct 5 ms 1780 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10096 KB Output is correct
2 Correct 31 ms 10088 KB Output is correct
3 Correct 21 ms 6748 KB Output is correct
4 Correct 5 ms 1780 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 12508 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10096 KB Output is correct
2 Correct 31 ms 10088 KB Output is correct
3 Correct 21 ms 6748 KB Output is correct
4 Correct 5 ms 1780 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -