제출 #765406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765406		thinknoexit	Dreaming (IOI13_dreaming)	C++17	47 / 100	62 ms	18740 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
vector<pair<int, ll>> adj[100100];
bool vis[100100];
int big[100100];
ll dp[100100][2], mn, mx = 0;
void dfs(int v, int p = -1) {
    vis[v] = 1;
    for (auto& [x, w] : adj[v]) {
        if (x == p) continue;
        dfs(x, v);
        dp[v][1] = max(dp[v][1], dp[x][0] + w);
        if (dp[v][1] > dp[v][0]) swap(dp[v][0], dp[v][1]), big[v] = x;
    }
}
void dfs2(int v, int p = -1, ll prev = 0) {
    dp[v][1] = max(dp[v][1], prev);
    if (dp[v][1] > dp[v][0]) swap(dp[v][0], dp[v][1]);
    mn = min(mn, dp[v][0]);
    mx = max(mx, dp[v][0] + dp[v][1]);
    for (auto& [x, w] : adj[v]) {
        if (x == p) continue;
        if (x == big[v]) dfs2(x, v, max(prev, dp[v][1]) + w);
        else dfs2(x, v, max(prev, dp[v][0]) + w);
    }
}
int travelTime(int n, int m, int L, int a[], int b[], int c[]) {
    memset(big, -1, sizeof big);
    for (int i = 0;i < m;i++) {
        adj[a[i]].push_back({ b[i],c[i] });
        adj[b[i]].push_back({ a[i],c[i] });
    }
    vector<ll> ans;
    for (int i = 0;i < n;i++) {
        if (vis[i]) continue;
        mn = 1e18;
        dfs(i);
        dfs2(i);
        ans.push_back(mn);
    }
    sort(ans.begin(), ans.end(), greater<int>());
    ll l = mx, r = 1e10;
    while (l < r) {
        ll mid = (l + r) / 2;
        ll nowmx = ans[0], tmx = 0;
        ll cnt = 0;
        bool ch = 1;
        for (int i = 1;i < (int)ans.size();i++) {
            cnt++;
            if (cnt * L + nowmx + ans[i] > mid) {
                cnt = 1;
                nowmx = max(nowmx, tmx);
                if (cnt * L + nowmx + ans[i] > mid) {
                    ch = 0;
                    break;
                }
            }
            tmx = max(tmx, ans[i] + cnt * L);
        }
        if (ch) r = mid;
        else l = mid + 1;
    }
    return l;
}
// int U[19], V[19], W[19];
// int main() {
//     int n, m, l;
//     cin >> n >> m >> l;
//     for (int i = 0;i < m;i++) {
//         cin >> U[i] >> V[i] >> W[i];
//     }
//     cout << travelTime(n, m, l, U, V, W);
// }
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23