Submission #1165618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165618		HappyCapybara	Dreaming (IOI13_dreaming)	C++17	100 / 100	118 ms	16908 KiB

dreaming

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

vector<bool> seen;
vector<vector<pair<int,int>>> g;

void calc(int i, unordered_map<int,int>& d){
    queue<pair<int,int>> q;
    q.push({i, 0});
    while (!q.empty()){
        int cur = q.front().first, dist = q.front().second;
        q.pop();
        seen[cur] = true;
        d[cur] = dist;
        for (pair<int,int> next : g[cur]){
            if (d.find(next.first) == d.end()) q.push({next.first, dist+next.second});
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.resize(N);
    for (int i=0; i<M; i++){
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    vector<int> rs;
    seen.resize(N, false);
    int ld = 0;
    for (int i=0; i<N; i++){
        if (seen[i]) continue;
        unordered_map<int,int> d1, d2;
        calc(i, d1);
        int bsf = -1, bo=i;
        for (auto &[i, d] : d1){
            if (d > bsf){
                bsf = d;
                bo = i;
            }
        }
        d1.clear();
        calc(bo, d1);
        bsf = -1;
        for (auto &[i, d] : d1){
            ld = max(ld, d);
            if (d > bsf){
                bsf = d;
                bo = i;
            }
        }
        calc(bo, d2);
        int res = pow(10, 9);
        for (auto &[i, d] : d1) res = min(res, max(d, d2[i]));
        rs.push_back(res);
    }
    if (M == N-1) return ld;
    sort(rs.begin(), rs.end());
    reverse(rs.begin(), rs.end());
    int res = ld;
    res = max(res, rs[0]+rs[1]+L);
    if (rs.size() > 2) res = max(res, rs[1]+rs[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