oj.uz

답안 #962090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962090 2024-04-13T06:56:38 Z danikoynov 꿈 (IOI13_dreaming) C++14
0 / 100
 32 ms 18540 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], sec[maxn];
void calc(int v, int p)
{
    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);
        int vl = max_depth[u] + nb.second;
        if (vl > max_depth[v])
        {
             sec[v] = max_depth[v];
             max_depth[v] = vl;
        }
        else
     if (vl > sec[v])
     {
          sec[v] = vl;
     }
        ///max_depth[v] = max(max_depth[v], max_depth[u] + nb.second);
    }
}
vector < int > ord;
void trav(int v, int p)
{
    ord.push_back(v);
    used[v] = 1;
    for (pair < int, int > nb : adj[v])
    {
        if (nb.first == p)
            continue;
        trav(nb.first, v);
    }
}

int dist;

void dfs(int v, int p, int lon)
{

    //cout << "dfs " << v << " " << p << " " << lon << endl;

    //cout << val << " " << sec << endl;
    dist = min(dist, max(lon, max_depth[v]));

    if (lon >= max_depth[v])
     return;

    for (pair < int, int > nb : adj[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        if (max_depth[u] + nb.second == max_depth[v])
        {
             dfs(u, v, max(lon, sec[v]) + nb.second);
             return;
        }
    }
}
int cap;

int path[maxn];
void bfs(int v)
{
    for (int w : ord)
        path[w] = -1;
    path[v] = 0;
    queue < int > q;
    q.push(v);
    while(!q.empty())
    {
        v = q.front();
        q.pop();
        for (pair <int, int > nb : adj[v])
        {
            if (path[nb.first] == -1)
            {
                path[nb.first] = path[v] + nb.second;
                q.push(nb.first);
            }
        }
    }
}
int find_distance(int v)
{
    ord.clear();
    trav(v, -1);
    dist = 2e9;
     calc(v, -1);
     dfs(v, -1, 0);

    bfs(v);
    int ds = v;
    for (int u : ord)
        if (path[u] > path[ds])
            ds = u;
    bfs(ds);
    for (int u : ord)
        if (path[u] > cap)
            cap = path[u];
    return dist;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[])
{

     int ds = 0;
    vector < int > tk;
    for (int i = 0; i < M; i ++)
    {
         ds = max(ds, T[i]);
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
        tk.push_back(T[i]);
    }

    for (int i = 0; i < N; i ++)
    {
         assert(adj[i].size() <= 1);
    }

     int lf = N - tk.size() * 2;
     for (int i = 0; i < lf; i ++)
          tk.push_back(0);
     sort(tk.begin(), tk.end());
     int tsz = tk.size();

     int op1 = max(ds, tk[tsz - 1] + tk[tsz - 2] + L);
     if (tsz > 2)
          op1 = max(op1, tk[tsz - 2] + tk[tsz - 3] + 2 * L);

     /**int op2 = max(ds, tk[tsz - 1] + tk[tsz - 2] + L);
     if (tsz > 2)
          op2 = max(op2, tk[tsz - 1] + tk[tsz - 3] + 2 * L);
     return min(op1, op2);*/
     return op1;

    //cout << find_distance(1) << endl;
    //exit(0);
    vector < int > 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();
    int res = values[sz - 1] + values[sz - 2] + L;

    if (sz >= 3)
        res = max(res, values[sz - 2] + values[sz - 3] + 2 * L);
    res = max(res, cap);
    return res;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 18540 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 11356 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 18540 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8024 KB Output is correct
2 Correct 12 ms 8152 KB Output is correct
3 Correct 12 ms 8028 KB Output is correct
4 Correct 20 ms 8024 KB Output is correct
5 Correct 13 ms 8020 KB Output is correct
6 Correct 17 ms 8408 KB Output is correct
7 Correct 12 ms 8152 KB Output is correct
8 Correct 14 ms 8032 KB Output is correct
9 Correct 13 ms 7944 KB Output is correct
10 Correct 12 ms 8284 KB Output is correct
11 Correct 1 ms 5724 KB Output is correct
12 Correct 3 ms 6360 KB Output is correct
13 Correct 5 ms 6360 KB Output is correct
14 Correct 3 ms 6360 KB Output is correct
15 Correct 3 ms 6360 KB Output is correct
16 Correct 3 ms 6360 KB Output is correct
17 Correct 3 ms 6360 KB Output is correct
18 Correct 3 ms 6360 KB Output is correct
19 Correct 4 ms 6380 KB Output is correct
20 Incorrect 1 ms 5724 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 11356 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 18540 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -