Submission #1181464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181464		jasonic	Dreaming (IOI13_dreaming)	C++20	100 / 100	74 ms	22972 KiB

dreaming

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

unordered_map<int, vector<pair<int, int>>> adjList;
bool vis[100005];
int d1[100005];
int d2[100005];
int r11[100005];
int r12[100005];
int r2[100005];
int farthest[100005];

void dp1(vector<int> &comp, int v, int p = -1) {

    comp.push_back(v);
    d1[v] = 0;

    int mxp1 = -1, mxp2 = -1;

    for(auto i : adjList[v]) if(i.first != p) {
        dp1(comp, i.first, v);
        int pl = d1[i.first] + i.second;
        d1[v] = max(d1[v], pl);

        if(mxp1 < pl) {
            mxp2 = mxp1;
            mxp1 = pl;
        } else if (mxp2 < pl) mxp2 = pl;
    }

    if(mxp2 != -1) {
        d2[v] = mxp1+mxp2;
    }
}

void dp2(int v, int p = -1) {
    
    r11[v] = 0;
    r12[v] = 0;

    for(auto i : adjList[v]) if (i.first != p) {
        dp2(i.first, v);
        int pl = r11[i.first] + i.second;
        if(pl > r11[v]) {
            r12[v] = r11[v];
            r11[v] = pl;
        } else if (pl > r12[v]) r12[v] = pl;
    }
}

void dp3(int v, int p = -1) {

    for(auto i : adjList[v]) if (i.first != p) {
        r2[i.first] = max(r11[i.first]+i.second==r11[v]?r12[v]:r11[v], r2[v]) + i.second;

        dp3(i.first, v);
    }
}

pair<int, int> solve(int r) {

    vector<int> connComp;

    dp1(connComp, r);
    dp2(r);
    dp3(r);

    int d = 0;
    int rad = INT_MAX;
    for(auto i : connComp) {d = max(d, max(d1[i], d2[i])); rad = min(rad, max(r11[i], i==r?r11[i]:r2[i])); vis[i] = true;}

    return make_pair(d, rad);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
    for(int i = 0; i < N; i++) {
        vis[i] = false;
        d1[i] = -1;
        d2[i] = -1;
        r2[i] = 0;
    }

    for(int i = 0; i < M; i++) {
        adjList[A[i]].push_back({B[i], T[i]});
        adjList[B[i]].push_back({A[i], T[i]});
    }

    vector<int> radii;
    vector<int> diams;

    int comps = 0;

    for(int i = 0; i < N; i++) {
        if(!vis[i]) {
            pair<int, int> ans = solve(i);
            diams.push_back(ans.first);
            radii.push_back(ans.second);
            comps++;
        }
    }

    sort(radii.begin(), radii.end(), greater<int>());
    sort(diams.begin(), diams.end(), greater<int>());
    
    if(comps == 1) {
        return diams[0];
    } else if (comps == 2) {
        return max(diams[0], radii[0] + radii[1] + L);
    } else {
        return max({diams[0], radii[0] + radii[1] + L, radii[1] + radii[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