Submission #56234

#	Time	Username	Problem	Language	Result	Execution time	Memory
56234		aquablitz11	Dreaming (IOI13_dreaming)	C++14	100 / 100	163 ms	19452 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

using pii = pair<int, int>;
using pp = pair<pii, pii>;
#define F first
#define S second

const int N = 100010;
const int INF = 1e9;

inline void setmax(pp &p, pii x) {
    if (x > p.F) {
        p.S = p.F;
        p.F = x;
    } else if (x > p.S) {
        p.S = x;
    }
}

inline pii getmax(pp p, int x=-1) {
    if (p.F.S == x) return p.S;
    return p.F;
}

vector<pii> G[N];
pp dp1[N], dp2[N];
bool vis[N];

int dfs1(int u, int p) {
    vis[u] = true;
    pp mx(pii(0, 0), pii(0, 0));
    int ans = 0;
    for (auto v : G[u]) if (v.F != p) {
        ans = max(ans, dfs1(v.F, u));
        setmax(mx, pii(getmax(dp1[v.F]).F + v.S, v.F));
    }
    dp1[u] = mx;
    ans = max(ans, mx.F.F + mx.S.F);
    return ans;
}

pii dfs2(int u, int p, int w) {
    pp mx = dp1[u];
    if (p != -1)
        setmax(mx, pii(getmax(dp2[p], u).F + w, p));
    dp2[u] = mx;
    pii ans(dp2[u].F.F, u);
    for (auto v : G[u]) if (v.F != p)
        ans = min(ans, dfs2(v.F, u, v.S));
    return ans;
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {

    for (int i = 0; i < m; ++i) {
        G[A[i]].emplace_back(B[i], T[i]);
        G[B[i]].emplace_back(A[i], T[i]);
    }
    vector<pii> add;
    for (int u = 0; u < n; ++u) {
        if (vis[u]) continue;
        dfs1(u, -1);
        add.push_back(dfs2(u, -1, -1));
    }
    sort(add.begin(), add.end(), greater<pii>());
    for (int i = 1; i < add.size(); ++i) {
        int u = add[0].S, v = add[i].S;
        G[u].emplace_back(v, L);
        G[v].emplace_back(u, L);
    }
    for (int u = 0; u < n; ++u) vis[u] = false;
    return dfs1(0, -1);

}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < add.size(); ++i) {
                     ~~^~~~~~~~~~~~

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