제출 #520820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520820		noob_c0de	꿈 (IOI13_dreaming)	C++17	77 / 100	89 ms	17476 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
// #define int long long
#define ar array
#define db double
#define sz(x) (int)x.size()
const db pi = acos(-1);
const int mxn = 1e5 + 7;
int in[mxn], out[mxn];
int vis[mxn];
vector<ar<int, 2> > g[mxn];
int diam, dist;
int d(int u)    
{
    return in[u] + out[u];
}
int leaf(int u)
{
    return max(in[u], out[u]);
}
void dfs(int u)
{
    vis[u] = 1;
    for (auto [v, w] : g[u])
    {
        if (vis[v]) continue;
        dfs(v);
        diam = max(diam, in[u] + in[v] + w);
        in[u] = max(in[u], in[v] + w);
    }
}
void dfs2(int u, int p)
{
    int mx1 = 0, mx2 = 0;
    for (auto [v, w] : g[u])
    {
        if (v == p) continue;
        if (in[v] + w > mx1) mx2 = mx1, mx1 = in[v] + w;
        else mx2 = max(mx2, in[v] + w);
    }
    for (auto [v, w] : g[u])
    {
        if (v == p) continue;
        if (in[v] + w == mx1) out[v] = max(out[u], mx2) + w;
        else out[v] = max(out[u], mx1) + w;
        dfs2(v, u);
    }
    dist = min(dist, leaf(u));
}   
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
    for (int i = 0; i < m; i++)
    {
        g[a[i] + 1].push_back({b[i] + 1, t[i]});
        g[b[i] + 1].push_back({a[i] + 1, t[i]});
    }
    vector<int> ans;
    int mx = 0;
    for (int i = 1; i <= n; i++)
    if (!vis[i]) 
    {
        dist = mxn;
        diam = 0;
        dfs(i);
        dfs2(i, i);
        ans.push_back(dist);
        mx = max(mx, diam);
        // cout << i - 1 << ' ' << tmp << '\n';
    }
    sort(ans.rbegin(), ans.rend());
    if (sz(ans) >= 2) mx = max(mx, ans[0] + ans[1] + l);
    if (sz(ans) >= 3) mx = max(mx, ans[1] + ans[2] + 2 * l);
    return mx;
};
// int n, m, l;
// int a[mxn], b[mxn], t[mxn];
// signed main()
// {
//     ios::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     // De nghi ko bat ultra instinct tay nhanh hon nao luc lam bai
//     cin >> n >> m >> l;
//     for (int i = 0; i < m; i++) 
//     {
//         cin >> a[i] >> b[i] >> t[i];
//     }
//     cout << travelTime(n, m, l, a, b, t);
//     /*
//     12 8 2
//     0 8 4
//     8 2 2
//     2 7 4
//     5 11 3
//     5 1 7
//     1 3 1
//     1 9 5
//     10 6 3*/
//     return 0;
// }

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