Submission #1258620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258620		goulthen	Dreaming (IOI13_dreaming)	C++20	100 / 100	62 ms	15760 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int,int>;

const int MAXN = 1e5+10;
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

vector<pii> g[MAXN];
bool mk[MAXN];
int dist[MAXN][2];

pii dfs(int u, int p = -1) {
    pii ans={0,u};
    mk[u] = 1;
    for (auto &[v,w] : g[u]) {
        if (v == p) continue;
        pii x = dfs(v,u);
        x.fi+=w;
        ans = max(ans, x);
    } 
    return ans;
}

void dfs2(int u, int k, int p = -1) {
    for (auto &[v,w] : g[u]) {
        if (v==p) continue;
        dist[v][k] = dist[u][k] + w;
        dfs2(v,k,u);
    }
}

int dfs3(int u, int p = -1) {
    int x = max(dist[u][0], dist[u][1]);
    for (auto &[v,w] : g[u]) {
        if (v==p)continue;
        x = min(x, dfs3(v,u));
    }
    return x;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    rep(i,0,M-1) {
        g[A[i]].emplace_back(B[i], T[i]);
        g[B[i]].emplace_back(A[i], T[i]);
    }
    vector<int> mxd;
    int ans = 0;
    rep(i,0,N-1) {
        if (mk[i]) continue;

        auto [_, c1] = dfs(i);
        auto [d, c2] = dfs(c1);

        dfs2(c1,0);
        dfs2(c2,1);
        ans = max(ans,d);

        mxd.push_back(dfs3(i));
    }

    sort(all(mxd), greater<int>());
    if (mxd.size() > 1) {
        ans = max(ans, L+mxd[0]+mxd[1]);
    } 
    if (mxd.size() > 2) {
        ans = max(ans, 2*L + mxd[1] + mxd[2]);
    }
    return ans;
}

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