제출 #1268864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268864		gotkako	Dreaming (IOI13_dreaming)	C++20	100 / 100	90 ms	44104 KiB

dreaming

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

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<vector<pair<int,long long>>> Graph(N);
    for(int i=0; i<M; i++){
        int u = A[i],v = B[i],w = T[i];
        Graph.at(u).push_back({v,w});
        Graph.at(v).push_back({u,w});
    }

    vector<bool> already(N);
    vector<int> par(N,-1);
    vector<vector<long long>> kid(N);
    vector<long long> dist;
    long long answer = 0;
    for(int i=0; i<N; i++) if(already.at(i) == false){
        {
            auto dfs = [&](auto dfs,int pos,int back) -> long long {
                already.at(pos) = true;
                kid.at(pos).resize(Graph.at(pos).size());
                long long ret = 0;
                for(int i=0; i<Graph.at(pos).size(); i++){
                    auto [to,w] = Graph.at(pos).at(i);
                    if(to == back) par.at(pos) = i;
                    else{
                        long long k = dfs(dfs,to,pos)+w;
                        kid.at(pos).at(i) = k;
                        ret = max(ret,k);
                    }
                }
                return ret;
            };
            dfs(dfs,i,-1);
        }
        {
            long long now = numeric_limits<long long>::max();
            auto dfs = [&](auto dfs,int pos,int back,long long take) -> void {
                if(back != -1) kid.at(pos).at(par.at(pos)) = take;
                auto L = kid.at(pos),R = L;
                if(L.size() == 0){now = 0; return;}
                for(int i=1; i<L.size(); i++) L.at(i) = max(L.at(i),L.at(i-1));
                for(int i=(int)R.size()-2; i>=0; i--) R.at(i) = max(R.at(i),R.at(i+1));
                now = min(now,L.back());
                answer = max(answer,L.back());
                for(int i=0; i<Graph.at(pos).size(); i++){
                    auto [to,w] = Graph.at(pos).at(i);
                    if(to == back) continue;
                    long long give = 0;
                    if(i) give = L.at(i-1);
                    if(i+1 < Graph.at(pos).size()) give = max(give,R.at(i+1));
                    give += w;
                    dfs(dfs,to,pos,give);
                }
            };
            dfs(dfs,i,-1,-1);
            dist.push_back(now);
        }
    }
    sort(dist.rbegin(),dist.rend());
    if(M == N-1) return max(answer,dist.at(0));
    else if(M == N-2) return max(answer,dist.at(0)+dist.at(1)+L);
    else return max(answer,max(dist.at(0)+dist.at(1)+L,dist.at(1)+dist.at(2)+L+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