Submission #225837

#	Time	Username	Problem	Language	Result	Execution time	Memory
225837		DS007	Dreaming (IOI13_dreaming)	C++14	47 / 100	169 ms	27768 KiB

dreaming

#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, temp.second});
    }
    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 (stderr)

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: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23