oj.uz

답안 #225844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225844 2020-04-21T20:21:27 Z DS007 꿈 (IOI13_dreaming) C++14
0 / 100
 88 ms 20728 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int MN = 1e5 + 5;
vector<pair<int, int>> adj[MN];
bool explored[MN];
vector<int> dia, dist;
multimap<int, int> m[MN];
int dp[MN];

int dfs(int v, int p = -1, int last = 0) {
    int val = max(last, dp[v]);
    for (auto i : adj[v]) {
        if (i.first == p)
            continue;

        auto itr = m[v].rbegin();
        if (itr->second == i.first && m[v].size() == 1)
            val = min(val, dfs(i.first, v, last + i.second));
        else if (itr->second == i.first)
            val = min(val, dfs(i.first, v, max(last, (++itr)->first) + i.second));
        else
            val = min(val, dfs(i.first, v, max(last, itr->first) + i.second));
    }

    dp[v] = max(dp[v], last);
    return val;
}

void pre(int v) {
    explored[v] = true;
    for (auto i : adj[v]) {
        if (!explored[i.first])
            pre(i.first), m[v].insert({dp[i.first] + i.second, i.first});
    }
    dp[v] = m[v].empty() ? 0 : m[v].rbegin()->first;
}

pair<int, int> longest(int v, int p = -1) {
    pair<int, int> ans = {0, v};
    for (auto i : adj[v]) {
        if (i.first == p)
            continue;

        auto temp = longest(i.first, v);
        ans = max(ans, {temp.first + i.second, i.first});
    }
    return ans;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        adj[A[i]].emplace_back(B[i], T[i]);
        adj[B[i]].emplace_back(A[i], T[i]);
    }

    for (int i = 0; i < N; i++) {
        if (!explored[i]) {
            pre(i), dist.push_back(dfs(i));
            auto temp = longest(i);
            dia.push_back(longest(temp.second).first);
        }
    }

    sort(dist.begin(), dist.end());

    pair<int, int> pen[dist.size()];
    int lp = 0, rp = dist.size() - 1;
    bool check = true;

    for (int i = 0; i < dist.size(); i++) {
        if (check)
            pen[i] = {lp++, dist[i]};
        else
            pen[i] = {rp--, dist[i]};
        check = !check;
    }

    sort(pen, pen + dist.size());

    int ans = *max_element(dia.begin(), dia.end()), temp = 0;
    for (int i = 0; i < dist.size(); i++) {
        ans = max(ans, temp + pen[i].second);
        temp = max(temp, pen[i].second) + L;
    }

    return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < dist.size(); i++) {
                     ~~^~~~~~~~~~~~~
dreaming.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < dist.size(); i++) {
                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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