oj.uz

Submission #850775

# Submission time Handle Problem Language Result Execution time Memory
850775 2023-09-17T12:25:03 Z aykhn Dreaming (IOI13_dreaming) C++14
0 / 100
 35 ms 13772 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define pb push_back
#define ins insert
#define pii pair<int, int>
#define fi first
#define se second
#define mpr make_pair
#define inf 0x3F3F3F3F

const int MXN = 1e5 + 5;

int n, m, l;
vector<pii> adj[MXN];
vector<vector<int>> comp;
int used[MXN];
int dist[2][MXN];
int c = -1;
int mx, node = -1;
int dia1, dia2;

void dfs(int a)
{
    comp[c].pb(a);
    used[a] = 1;
    for (pii v : adj[a])
    {
        if (used[v.fi]) continue;
        dfs(v.fi);
    }
}

void dfs1(int a, int w = 0, int p = -1)
{
    if (w > mx)
    {
        mx = w;
        dia2 = a;
    }
    for (pii v : adj[a])
    {
        if (v.fi == p) continue;
        dfs1(v.fi, w + v.se, a);
    }
}

void dfs2(int a, int id, int w = 0, int p = -1)
{
    dist[id][a] = w;
    for (pii v : adj[a])
    {
        if (v.fi == p) continue;
        dfs2(v.fi, id, w + v.se, a);
    }
}

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]].pb(mpr(B[i], T[i]));
        adj[B[i]].pb(mpr(A[i], T[i]));
    }
    for (int i = 0; i < n; i++)
    {
        if (!used[i])
        {
            c++;
            comp.pb(vector<int> (0));
            dfs(i);
        }
    }
    multiset<int> ms;

    for (int i = 0; i <= c; i++)
    {
        mx = -inf;
        dia1 = dia2 = -1;
        dfs1(comp[i][0]);
        mx = -inf;
        dia1 = dia2;
        dfs1(dia1);
        dfs2(dia1, 0);
        dfs2(dia2, 1);
        int center = comp[i][0];
        for (int u : comp[i])
        {
            if (max(dist[0][u], dist[1][u]) < max(dist[0][center], dist[1][center])) center = u;
        }
        ms.ins(max(dist[0][center], dist[1][center]));
    }

    if (!c) return *ms.begin();
    auto it = ms.end();
    it--;
    it--;
    return *ms.rbegin() + *it + l;
}

Subtask #1
0 / 14.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13320 KB Output is correct
2 Incorrect 31 ms 13772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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