제출 #468033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468033		SirCovidThe19th	꿈 (IOI13_dreaming)	C++17	0 / 100	52 ms	14020 KiB

dreaming

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

#define pii pair<int, int>
#define f first
#define s second

const int mx = 1e5 + 5, inf = 1e9;

vector<pair<int, int>> adj[mx]; pii in[mx]; bool vis[mx];

void dfs1(int i, int p){
    vis[i] = 1;
    for (auto [x, w] : adj[i]) if (x != p){
        dfs1(x, i); 
        if (in[x].f + w > in[i].f) in[i].s = in[i].f, in[i].f = in[x].f + w;
        else if (in[x].f + w > in[i].s) in[i].s = in[x].f + w;
    }
}
void dfs2(int i, int p, int pout, int &far){
    far = min(far, pout + in[i].f);
    for (auto [x, w] : adj[i]) if (x != p){
        int sib = (in[i].f == in[x].f + w) ? in[i].s : in[i].f;
        int out = max(sib + in[x].f + w, far);
        dfs2(x, i, out, far);
    }
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]){
    for (int i = 0; i < m; i++){
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    int w[3] = {-inf, -inf, -inf};
    for (int i = 1, far; i <= n; i++) if (!vis[i]){
        dfs1(i, 0); dfs2(i, 0, 0, far);
        if (far > w[0]) w[2] = w[1], w[1] = w[0], w[0] = far;
        else if (far > w[1]) w[2] = w[1], w[1] = far;
        else if (far > w[2]) w[2] = far;
    }
    return max(w[1] + w[2] + l * 2, w[0] + w[1] + l);
}

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