Submission #833060

#	Time	Username	Problem	Language	Result	Execution time	Memory
833060		SoulKnight	Dreaming (IOI13_dreaming)	C++17	100 / 100	49 ms	17456 KiB

dreaming

#include "dreaming.h"
// #include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <bitset>
#include <cstring>
#include <algorithm>

using namespace std;

#define ll long long
#define ln '\n'

const int N = 1e5 + 5;
const int INF = 1e9;


vector<pair<int, int>> adj[N];
int fir[N], sec[N], ans[N];

// int mn = INF, which = -1;
// vector<pair<int, int>> leader;

int mn = INF, mx = 0, final = 0;
vector<int> leader;

void dfs1(int u, int p){
    for (auto& [e, v]: adj[u]){
        if (v == p) continue;
        dfs1(v, u);
        if (fir[v] + e > fir[u]){
            sec[u] = fir[u];
            fir[u] = fir[v] + e;
        } else if (fir[v] + e > sec[u]){
            sec[u] = fir[v] + e;
        }
    }
}

void dfs2(int u, int p, int to_p){
    ans[u] = max(to_p, fir[u]);
    // if (ans[u] < mn){
    //     mn = ans[u];
    //     which = u;
    // }
    mn = min(mn, ans[u]);
    mx = max(mx, ans[u]);

    for (auto& [e, v]: adj[u]){
        if (v == p) continue;
        if (fir[v] + e == fir[u]){
            dfs2(v, u, max(to_p, sec[u])+e);
        } else dfs2(v, u, ans[u]+e);
    }
}

void getLongestPath(int u){
    dfs1(u, -1);
    dfs2(u, -1, 0);
}

int travelTime(int NN, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++){
        adj[A[i]].push_back({T[i], B[i]});
        adj[B[i]].push_back({T[i], A[i]});
    }
    memset(ans, -1, sizeof(ans));

    for (int i = 0; i < NN; i++){
        if (ans[i] != -1) continue;
        mn = INF; mx = 0;
        getLongestPath(i); // tree rooted at i
        // leader.push_back({mn, which});
        final = max(final, mx);
        leader.push_back(mn);
    }


    // for (int i = 0; i < NN; i++){
    //     cout << ans[i] << ' ';
    // }
    // cout << ln;

    sort(leader.begin(), leader.end());
    // for (auto& u: leader) cout << u << ' ';
    // cout << ln;
    int k = leader.size();

    if (k == 1) return max(final, leader[k-1]);
    if (k == 2) return max(final, leader[k-1] + leader[k-2] + L);
    else return max(final, max(leader[k-1] + leader[k-2] + L,
                    leader[k-2] + leader[k-3] + 2*L));
}

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