oj.uz

Submission #426491

# Submission time Handle Problem Language Result Execution time Memory
426491 2021-06-14T05:21:17 Z Aldas25 Dreaming (IOI13_dreaming) C++14
0 / 100
 59 ms 13268 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i<= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;

const int MAXN = 100100;
const ll INF = 1e15;

int n, m;
ll l;
vii adj[MAXN];

ll dp[MAXN][2];
bool vis[MAXN];

ll mx, sm;

void dfs1 (int v, int p = -1) {
    vis[v] = true;
    for (auto pp : adj[v]) {
        int u = pp.f;
        ll w = pp.s;
        if (u == p) continue;
        dfs1(u, v);

        ll cr = dp[u][0] + w;
        if (cr > dp[v][1]) dp[v][1] = cr;
        if (dp[v][1] > dp[v][0]) swap(dp[v][0], dp[v][1]);
    }

    mx = max(mx, dp[v][0]+dp[v][1]);

    //cout << " v = " << v << " dp0 = " << dp[v][0] << " dp1 = " << dp[v][1] << endl;
}

void dfs2 (int v, int p = -1, ll prevW = 0) {
    if (p != -1) {
        ll cr = 0;
        if (dp[p][0] != dp[v][0] + prevW)
            cr = dp[p][0] + prevW;
        else
            cr = dp[p][1] + prevW;

        if (cr > dp[v][1]) dp[v][1] = cr;
        if (dp[v][1] > dp[v][0]) swap(dp[v][0], dp[v][1]);
    }

    for (auto pp : adj[v]) {
        int u = pp.f;
        ll w = pp.s;
        if (u == p) continue;
        dfs2(u, v, w);
    }

    sm = min(sm, dp[v][0]);

    //cout << " dfs2 v = " << v << " dp0 = " << dp[v][0] << " dp1 = " << dp[v][1] << endl;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    m = M;
    l = L;
    FOR(i, 0, m-1) {
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }

    ll ans = 0;
    ll cur = l;
    FOR(i, 0, n-1) {
        if (vis[i]) continue;
        mx = 0;
        dfs1 (i);
        ans = max(mx, ans);

        sm = INF;
        dfs2 (i);
        cur += sm;
    }
    ans = min(ans, cur);

    return ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 13268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 13268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 6964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 13268 KB Output isn't correct
2 Halted 0 ms 0 KB -