Submission #834316

#	Time	Username	Problem	Language	Result	Execution time	Memory
834316		PixelCat	Dreaming (IOI13_dreaming)	C++17	100 / 100	84 ms	17068 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100'000;

vector<pii> adj[MAXN +  10];
int h1[MAXN + 10];
int h2[MAXN + 10];

inline void link(int a, int b, int c) {
    adj[a].eb(b, c);
    adj[b].eb(a, c);
}

void dfs1(int n, int p) {
    h1[n] = 0;
    for(auto &e:adj[n]) if(e.F != p) {
        dfs1(e.F, n);
        int h = h1[e.F] + e.S;
        if(h > h1[n]) {
            h2[n] = h1[n];
            h1[n] = h;
        } else if(h > h2[n]) {
            h2[n] = h;
        }
    }
}

int mnh, mni;
void dfs2(int n, int p, int h3) {
    int h = max(h3, h1[n]);
    if(h < mnh) {
        mnh = h;
        mni = n;
    }
    for(auto &e:adj[n]) if(e.F != p) {
        int h4 = h1[n];
        if(h4 == h1[e.F] + e.S) h4 = h2[n];
        h4 = max(h4, h3) + e.S;
        dfs2(e.F, n, h4);
    }
}

// {depth, index}
pii dfs3(int n, int p) {
    pii res(0, n);
    for(auto &e:adj[n]) if(e.F != p) {
        pii r2 = dfs3(e.F, n);
        r2.F += e.S;
        res = max(res, r2);
    }
    return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    For(i, 0, M - 1) {
        link(A[i], B[i], T[i]);
    }
    memset(h1, -1, sizeof(h1));
    vector<pii> rt;  // {height, index}
    For(i, 0, N - 1) if(h1[i] == -1) {
        dfs1(i, i);
        mnh = 2e9; mni = -1;
        dfs2(i, i, 0);
        rt.eb(mnh, mni);
    }
    sort(all(rt));
    For(i, 0, sz(rt) - 2) {
        link(rt.back().S, rt[i].S, L);
    }
    return dfs3(dfs3(0, 0).S, -1).F;
}



#ifdef NYAOWO

const int _MAXN = 100'000;
int _A[_MAXN + 10];
int _B[_MAXN + 10];
int _T[_MAXN + 10];

int32_t main() {
    int n, m, l; cin >> n >> m >> l;
    For(i, 0, m - 1) {
        cin >> _A[i];
        cin >> _B[i];
        cin >> _T[i];
    }
    int ret = travelTime(n, m, l, _A, _B, _T);
    cout << ret << "\n";
    return 0;
}

#endif

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