Submission #1301951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301951		regulardude6	꿈 (IOI13_dreaming)	C++20	59 / 100	1096 ms	10500 KiB

dreaming

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

using ll = long long;

struct Edge{ int to, w; };

static pair<int,ll> farthest(int src, const vector<vector<Edge>>& g, const vector<int>& nodes, const vector<char>& inComp, vector<ll>* outDist) {
    vector<ll> dist(g.size(), -1);
    vector<int> st;
    st.reserve(nodes.size());
    st.push_back(src);
    dist[src] = 0;

    vector<int> par(g.size(), -1);
    while(!st.empty()){
        int v = st.back(); st.pop_back();
        for(auto e: g[v]){
            int u = e.to;
            if(!inComp[u]) continue;
            if(u == par[v]) continue;
            if(dist[u] != -1) continue;
            par[u] = v;
            dist[u] = dist[v] + e.w;
            st.push_back(u);
        }
    }

    int bestV = src;
    ll bestD = 0;
    for(int v: nodes){
        if(dist[v] > bestD){
            bestD = dist[v];
            bestV = v;
        }
    }

    if(outDist) *outDist = std::move(dist);
    return {bestV, bestD};
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<vector<Edge>> g(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<char> vis(N, 0), inComp(N, 0);
    vector<ll> radii;
    ll maxDiam = 0;

    for(int i=0;i<N;i++) if(!vis[i]){
        vector<int> nodes;
        stack<int> st;
        st.push(i);
        vis[i] = 1;

        while(!st.empty()){
            int v = st.top(); st.pop();
            nodes.push_back(v);
            inComp[v] = 1;
            for(auto e: g[v]){
                int u = e.to;
                if(!vis[u]){
                    vis[u] = 1;
                    st.push(u);
                }
            }
        }

        auto a = farthest(nodes[0], g, nodes, inComp, nullptr);

        vector<ll> da, db;
        auto b = farthest(a.first, g, nodes, inComp, &da);
        auto c = farthest(b.first, g, nodes, inComp, &db);

        maxDiam = max(maxDiam, c.second);

        ll rad = (ll)4e18;
        for(int v: nodes) rad = min(rad, max(da[v], db[v]));
        radii.push_back(rad);

        for(int v: nodes) inComp[v] = 0;
    }

    sort(radii.begin(), radii.end(), greater<ll>());

    ll ans = maxDiam;
    if((int)radii.size() >= 2) ans = max(ans, radii[0] + (ll)L + radii[1]);
    if((int)radii.size() >= 3) ans = max(ans, radii[1] + 2LL*(ll)L + radii[2]);

    return (int)ans;
}

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