Submission #394429

#	Time	Username	Problem	Language	Result	Execution time	Memory
394429		phathnv	Dreaming (IOI13_dreaming)	C++11	100 / 100	123 ms	37572 KiB

dreaming

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

using namespace std;

const int N = 1e5 + 7;

vector<pair<int, int>> adj[N];
int down[N], up[N], dp[N];
bool vst[N];

void Dfs1(int u, int p){
    vst[u] = 1;
    down[u] = dp[u] = 0;
    for(auto e : adj[u]){
        int v = e.first;
        int c = e.second;
        if (v == p)
            continue;
        Dfs1(v, u);
        dp[u] = max(dp[u], down[u] + down[v] + c);
        dp[u] = max(dp[u], dp[v]);
        down[u] = max(down[u], down[v] + c);
    }
}

void Dfs2(int u, int p, int &best){
    best = min(best, max(up[u], down[u]));
    multiset<int> s;
    s.insert(up[u]);
    for(auto e : adj[u]){
        int v = e.first;
        int c = e.second;
        if (v == p)
            continue;
        s.insert(down[v] + c);
    }
    for(auto e : adj[u]){
        int v = e.first;
        int c = e.second;
        if (v == p)
            continue;
        s.erase(s.find(down[v] + c));
        up[v] = *(--s.end()) + c;
        s.insert(down[v] + c);
        Dfs2(v, u, best);
    }
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for(int i = 0; i < m; i++){
        adj[a[i]].push_back({b[i], t[i]});
        adj[b[i]].push_back({a[i], t[i]});
    }
    int res = 0;
    vector<int> vals;
    for(int i = 0; i < n; i++){
        if (vst[i])
            continue;
        int best = 1e9;
        Dfs1(i, -1);
        Dfs2(i, -1, best);
        res = max(res, dp[i]);
        vals.push_back(best);
    }
    sort(vals.begin(), vals.end(), greater<int>());
    if (vals.size() >= 2)
        res = max(res, vals[0] + vals[1] + l);
    if (vals.size() >= 3)
        res = max(res, vals[1] + vals[2] + 2 * l);
    return res;
}

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