Submission #1024590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024590		socpite	Dreaming (IOI13_dreaming)	C++17	100 / 100	63 ms	16644 KiB

dreaming

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

const int maxn = 1e5+5;
const int INF = 1e9+5;

vector<pair<int, int>> g[maxn];

int d1[maxn], d2[maxn], vis[maxn];

vector<int> vec;

void pre_dfs(int x, int p){
    vis[x] = 1;
    vec.push_back(x);
    for(auto v: g[x]){
        if(v.first == p)continue;
        pre_dfs(v.first, x);
    }
}

void dfs(int x, int p, int* D){
    if(p == -1)D[x] = 0;
    for(auto v: g[x]){
        if(v.first == p)continue;
        D[v.first] = D[x] + v.second;
        dfs(v.first, x, D);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int ans = 0;
    vector<int> hdm;
    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]});
    }
    for(int i = 0; i < N; i++){
        if(vis[i])continue;
        vec.clear();
        pre_dfs(i, -1);
        dfs(i, -1, d1);
        int rt1 = i;
        for(auto v: vec)if(d1[v] > d1[rt1])rt1 = v;
        dfs(rt1, -1, d1);
        int rt2 = i;
        for(auto v: vec)if(d1[v] > d1[rt2])rt2 = v;
        dfs(rt2, -1, d2);
        ans = max(ans, d1[rt2]);

        int mn = INF;
        for(auto v: vec){
            mn = min(mn, max(d1[v], d2[v]));
        }
        hdm.push_back(mn);
    }
    sort(hdm.rbegin(), hdm.rend());
    if(hdm.size() >= 2)ans = max(ans, hdm[0] + hdm[1] + L);
    if(hdm.size() >= 3)ans = max(ans, hdm[1] + hdm[2] + 2*L);
    return ans;
}

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