oj.uz

답안 #367105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367105 2021-02-16T09:59:32 Z idk321 꿈 (IOI13_dreaming) C++11
0 / 100
 339 ms 28652 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<int> comp;

int dfs1(int node, int par)
{
    vis[node] = true;
    int res = 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)
{

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


    cout << node << " " << res << endl;
    for (auto next : adj[node])
    {

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

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


    return res;
}


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);
            comp.push_back(dfs2(i, -1, -1));
        }
    }

    return comp[0] + comp[1] + l;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 339 ms 28652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 339 ms 28652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 271 ms 14440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 339 ms 28652 KB Output isn't correct
2 Halted 0 ms 0 KB -