oj.uz

Submission #367132

# Submission time Handle Problem Language Result Execution time Memory
367132 2021-02-16T10:39:58 Z idk321 Dreaming (IOI13_dreaming) C++11
0 / 100
 159 ms 34028 KB 
    #include "dreaming.h"

    #include <bits/stdc++.h>
    using namespace std;

    int n, m, l;
    const int N =100005;
    bool vis[N];
    multiset<int> ms[N];
    vector<array<int, 2>> adj[N];
    vector<array<int, 2>> comp;

    int dfs1(int node, int par)
    {
        vis[node] = true;
        int res = 0;
        ms[node].insert(0);
        for (auto next : adj[node])
        {
            if (next[0] == par) continue;
            int cur = dfs1(next[0], node) + next[1];
            res = max(res, cur);
            ms[node].insert(cur);
        }

        return res;
    }

    int dfs2(int node, int par, int pdist)
    {

        if (par != -1)
        {
            int del = *ms[node].rbegin() + pdist;
            ms[par].erase(ms[par].find(del));
            ms[node].insert(*ms[par].rbegin() + pdist);
            ms[par].insert(del);
        }
        int res = *ms[node].rbegin();


        for (auto next : adj[node])
        {

            if (next[0] == par) continue;

            res = min(res, dfs2(next[0], node, next[1]));
        }


        return res;
    }

    array<int, 2> dfs3(int node, int par)
    {
        array<int, 2> best = {node, 0};
        for (auto next : adj[node])
        {
            if (next[0] == par) continue;
            auto cur = dfs3(next[0],node);
            cur[1] += next[1];
            if (cur[1] > best[1])
            {
                best = cur;
            }
        }

        return best;
    }

    int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
        n = N;
        m = M;
        l = L;
        for (int i = 0; i < m; i++)
        {

            adj[A[i]].push_back({B[i], T[i]});
            adj[B[i]].push_back({A[i], T[i]});
        }


        for (int i = 0; i < n; i++)
        {
            if (!vis[i])
            {
                dfs1(i, -1);
                int cent = dfs2(i, -1, -1);
                auto cur = dfs3(i, -1);
                int mdist = dfs3(cur[0], -1)[1];

                comp.push_back({cent, mdist});
            }
        }

        return max({comp[0][0] + comp[1][0] + l, comp[0][1], comp[0][2]});
    }

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 32876 KB Output is correct
2 Correct 159 ms 34028 KB Output is correct
3 Correct 97 ms 24940 KB Output is correct
4 Correct 19 ms 11244 KB Output is correct
5 Incorrect 16 ms 9836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 6 ms 7552 KB Output is correct
7 Correct 6 ms 7404 KB Output is correct
8 Correct 6 ms 7404 KB Output is correct
9 Correct 5 ms 7404 KB Output is correct
10 Correct 5 ms 7404 KB Output is correct
11 Correct 5 ms 7404 KB Output is correct
12 Correct 5 ms 7404 KB Output is correct
13 Incorrect 5 ms 7404 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 32876 KB Output is correct
2 Correct 159 ms 34028 KB Output is correct
3 Correct 97 ms 24940 KB Output is correct
4 Correct 19 ms 11244 KB Output is correct
5 Incorrect 16 ms 9836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 6 ms 7552 KB Output is correct
7 Correct 6 ms 7404 KB Output is correct
8 Correct 6 ms 7404 KB Output is correct
9 Correct 5 ms 7404 KB Output is correct
10 Correct 5 ms 7404 KB Output is correct
11 Correct 5 ms 7404 KB Output is correct
12 Correct 5 ms 7404 KB Output is correct
13 Incorrect 5 ms 7404 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 32876 KB Output is correct
2 Correct 159 ms 34028 KB Output is correct
3 Correct 97 ms 24940 KB Output is correct
4 Correct 19 ms 11244 KB Output is correct
5 Incorrect 16 ms 9836 KB Output isn't correct
6 Halted 0 ms 0 KB -