Submission #1276186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276186		LeDaiKing	Dreaming (IOI13_dreaming)	C++20	0 / 100	36 ms	13324 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ALL(n) n.begin(), n.end()
#define mask(n) (1ll << (n))
#define ck(n, k) (((n) >> (k))&1)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void dfs1(int u, vector<vector<pair<int,int>>>& adj, vector<bool>& vis, vector<int>& dp1, vector<int>& dp2) {

    vis[u] = true;

    for (auto e: adj[u]) {
        if (vis[e.fi]) continue;
        int v = e.fi, t = e.se;
        dfs1(v, adj, vis, dp1, dp2);
        if (dp1[v] + t > dp1[u]) {
            dp2[u] = dp1[u];
            dp1[u] = dp1[v] + t;
        } else dp2[u] = max(dp2[u], dp1[v] + t);
    }
}

int dfs2(int u, int pa, int pathTo, vector<vector<pair<int,int>>>& adj, vector<int>& dp1, vector<int>& dp2, int& ans) {

    int res = max(pathTo, dp1[u]);
    ans = max(ans, res);

    for (auto e : adj[u]) {
        if (e.fi == pa) continue;
        int v = e.fi, t = e.se;
        if (dp1[u] == dp1[v] + t) res = min(res, dfs2(v, u, max(dp2[u], pathTo) + t, adj, dp1, dp2, ans));
        else res = min(res, dfs2(v, u, max(dp1[u], pathTo) + t, adj, dp1, dp2, ans));
    }
    return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    vector<vector<pair<int,int>>> adj(N);
    vector<bool> vis(N, false);
    vector<int> dp1(N, 0);
    vector<int> dp2(N, 0);
    for (int i = 0; i < M ;i++) {
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }
    int ans = 0, ans1 = -1, ans2 = -1;
    for (int i = 0; i < N; i++)
    if (!vis[i]) {

        dfs1(i, adj, vis, dp1, dp2);
         int cur = dfs2(i, -1, 0, adj, dp1, dp2, ans);
        if (cur > ans1) {
            ans2 = ans1;
            ans1 = cur;
        } else {
            ans2 = max(ans2, cur);
        }
    }

    if (ans1 != -1 && ans2 != -1) ans = min(ans, ans1 + ans2 + L);

    return ans;

}

// int main()
// {  
//     ios_base::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     int testcase = 1;
//     // cin >> testcase;
//     int n, m, l;
//     cin >> n >> m >> l;
//     int a[m], b[m], t[m];
//     for (int i = 0; i < m; i++) {
//         cin >> a[i] >> b[i] >> t[i];
//     }
//     cout << travelTime(n, m, l, a, b, t);
//     return 0;
// }

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