제출 #1318803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318803		okahak71	꿈 (IOI13_dreaming)	C++20	100 / 100	53 ms	17592 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll array<ll, 2>
using namespace std;

const ll N = 1e5 + 5;
const ll inf = INT_MAX;

bool bl = 0;
vector<vector<pll>>g;
ll ch[N]; pll par[N]; 
array<int, 2> mx = {-1, -1};

void dfs(ll u, ll p = -1, ll W = 0){
    ch[u] = 1;
    if(W > mx[1]) mx = {(int)u, (int)W};
    for(auto &[v, w]: g[u]){
        if(v == p) continue;
        par[v] = {u, w};
        dfs(v, u, W + w);
    }
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    g.assign(n, {});
    for(ll i = 0; i < m; i++){
        g[a[i]].pb({b[i], t[i]});
        g[b[i]].pb({a[i], t[i]});
    }
    vector<ll>r; int mxW = 0;
    for(ll i = 0; i < n; i++){
        if(ch[i]) continue;
        mx = {-1, -1}; dfs(i); 
        ll id = mx[0]; mx = {-1, -1}; 
        par[id] = {-1, 0}; dfs(id, 1);
        ll x = mx[0], W = 0, rad = inf;
        while(x >= 0){
            W += par[x][1];
            x = par[x][0];
            rad = min(rad, max(W, mx[1] - W));
        }
        r.pb(rad == inf ? 0 : rad); mxW = max(mxW, mx[1]);
    }
    sort(r.rbegin(), r.rend());
    if(r.size() < 2) return mxW;
    if(r.size() == 2) return max(mxW, int(r[0] + r[1] + l));
    return max({mxW, int(r[0] + r[1] + l), int(r[1] + r[2] + 2 * 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