oj.uz

Submission #962056

# Submission time Handle Problem Language Result Execution time Memory
962056 2024-04-13T06:24:47 Z danikoynov Dreaming (IOI13_dreaming) C++14
0 / 100
 27 ms 12040 KB 
#include "dreaming.h"
#include<bits/stdc++.h>


using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

vector < pair < int, int > > adj[maxn];

int used[maxn], depth[maxn];
int max_depth[maxn];
void calc(int v, int p)
{
    used[v] = 1;
    max_depth[v] = 0;
    for (pair < int, int > nb : adj[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        depth[u] = depth[v] + nb.second;
        calc(u, v);
        max_depth[v] = max(max_depth[v], max_depth[u] + nb.second);
    }
}

int dist;
void dfs(int v, int p, int lon)
{
     //cout << "dfs " << v << " " << p << " " << lon << endl;
    int val = lon, sec = 0;
    for (pair < int, int > nb : adj[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        if (max_depth[u] + nb.second > val)
        {
            sec = val;
            val = max_depth[u] + nb.second;
        }
        else if (max_depth[u] + nb.second > sec)
        {
            sec = max_depth[u] + nb.second;
        }
    }
     //cout << val << " " << sec << endl;
    dist = min(dist, val);
    if (val == lon)
        return;
    for (pair < int, int > nb : adj[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        if (val == max_depth[u] + nb.second)
        {
            dfs(u, v, sec + nb.second);
            return;
        }
    }
}
int find_distance(int v)
{
    calc(v, -1);
    dist = 2e9;
    dfs(v, -1, 0);
    return dist;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{

    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]});
    }

    //cout << find_distance(1) << endl;
    //exit(0);
    vector < ll > values;
    for (int i = 0; i < N; i ++)
    {
        if (!used[i])
            values.push_back(find_distance(i));
    }


    //for (int cur : values)
     //cout << cur << " ";
    //cout << endl;
    sort(values.begin(), values.end());

    int sz = values.size();
    ll res = values[sz - 1] + values[sz - 2] + L;
    if (sz >= 3)
        res = max(res, values[sz - 2] + values[sz - 3] + 2 * L);
    return res;
}

Subtask #1
0 / 14.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7644 KB Output is correct
2 Correct 13 ms 7640 KB Output is correct
3 Correct 13 ms 7648 KB Output is correct
4 Correct 14 ms 7680 KB Output is correct
5 Correct 13 ms 7608 KB Output is correct
6 Correct 17 ms 8392 KB Output is correct
7 Correct 19 ms 7644 KB Output is correct
8 Correct 13 ms 7648 KB Output is correct
9 Correct 13 ms 7464 KB Output is correct
10 Correct 14 ms 7892 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 4 ms 6100 KB Output is correct
13 Correct 4 ms 6068 KB Output is correct
14 Correct 4 ms 6100 KB Output is correct
15 Correct 4 ms 6100 KB Output is correct
16 Correct 4 ms 6128 KB Output is correct
17 Correct 3 ms 6096 KB Output is correct
18 Correct 4 ms 6104 KB Output is correct
19 Correct 4 ms 6100 KB Output is correct
20 Incorrect 1 ms 2908 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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