Submission #765415

#	Time	Username	Problem	Language	Result	Execution time	Memory
765415		thinknoexit	Dreaming (IOI13_dreaming)	C++17	100 / 100	63 ms	20372 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<ll>());
    if (ans.size() == 1) {
        return mx;
    }
    if (ans.size() == 2) {
        return max(mx, ans[0] + ans[1] + L);
    }
    return max({ mx,ans[0] + ans[1] + L, ans[1] + ans[2] + 2 * 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: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23