제출 #1192810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192810		adiyer	Dreaming (IOI13_dreaming)	C++20	47 / 100	51 ms	14608 KiB

dreaming

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

using namespace std;

typedef int ll;

const int N = 1e5 + 11;

int ans = 1e9, res = 0;

ll x, y;
ll d[N], d1[N], d2[N], was[N], par[N];

vector < pair < ll, ll > > g[N];

void dfs(ll v, ll p){
    was[v] = 1;
    if(x == -1 || d[v] > d[x]) x = v;
    for(auto [u, w] : g[v])
        if(u != p)
            par[u] = v, d[u] = d[v] + w, dfs(u, v);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(ll i = 0; i < N; i++) par[i] = -1;
    for(ll i = 0; i < M; i++) g[A[i]].push_back({B[i], T[i]});
    for(ll i = 0; i < M; i++) g[B[i]].push_back({A[i], T[i]});
    if(N - 1 == M) return 0;
    vector < ll > vec;
    multiset < ll > st;
    for(ll i = 0, v1, v2, dd; i < N; i++){
        if(!was[i]){
            x = -1, d[i] = 0, dfs(i, i), v1 = x;
            x = -1, d[v1] = 0, dfs(v1, v1), v2 = x;
            dd = d[v2], res = max(res, d[v2]);
            while(1){
                if(v1 == v2 || max(d[v2], dd - d[v2]) <= max(d[par[v2]], dd -  d[par[v2]])) break;
                v2 = par[v2];
            }
            vec.push_back(max(d[v2], dd - d[v2]));
            st.insert(max(d[v2], dd - d[v2]));
        }
    }
    for(ll val : vec){
        st.erase(st.find(val));
        int it = val + L + *st.rbegin(), jt = 0;
        if(st.size() > 1) jt = *st.rbegin() + *(--st.rbegin()) + 2 * L;
        ans = min(ans, max(it, jt));
        st.insert(val);
    }
    return max(ans, res);
}

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