제출 #1287665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287665		harryleee	Dreaming (IOI13_dreaming)	C++20	100 / 100	58 ms	16480 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int maxn = 1e5;
bool vis[maxn];
vector<pair<int, int>> adj[maxn];
int comp[maxn];
int cnt;

struct NODE{
    int max1, max2, id1, id2;
    inline NODE(){
        max1 = max2 = id1 = id2 = -1;
    }
} node[maxn];

void DFS(int u, int p){
    vis[u] = true;
    node[u].max1 = 0; node[u].id1 = u;
    for (auto [v, w] : adj[u]) if (v != p){
        DFS(v, u);
        if (node[v].max1 + w >= node[u].max1){
            node[u].max2 = node[u].max1;
            node[u].id2 = node[u].id1;
            node[u].max1 = node[v].max1 + w;
            node[u].id1 = v;
        }
        else if (node[v].max1 + w > node[u].max2){
            node[u].max2 = node[v].max1 + w;
            node[u].id2 = v;
        }
    }
    // cout << u << ' ' << node[u].max1 << ' ' << node[u].max2 << '\n';
    return;
}

int solve(int u, int p, int pre_len){
    int res = max(pre_len, node[u].max1);
    for (auto [v, w] : adj[u]) if (v != p){
        int down = pre_len + w;
        if (v != node[u].id1){
            down = max(down, node[u].max1 + w);
            res = min(res, solve(v, u, down));
        }
        else{
            down = max(down, node[u].max2 + w);
            res = min(res, solve(v, u, down));
        }
    }
    return res;
}

pair<int, int> parameter(int u, int p){
    pair<int, int> res = {0, u};
    for (auto [v, w] : adj[u]) if (v != p){
        pair<int, int> d = parameter(v, u);
        if (d.first + w > res.first)
            res.first = d.first + w, res.second = d.second;
    }
    return res;
}

int travelTime(int n, int m, int L, int a[], int b[], int t[]){
    int ans = 0;
    memset(vis, false, sizeof(vis));    
    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]});
    }

    for (int i = 0; i < n; ++i) if (!vis[i]){
        DFS(i, -1);
        comp[cnt] = solve(i, -1, 0); 
        pair<int, int> d = parameter(i, -1);
        d = parameter(d.second, -1);
        ans = max(ans, d.first);
        cnt++;
    }
    sort(comp, comp + cnt);
    int cur = comp[cnt - 1];
    for (int i = 0; i < cnt - 1; ++i){
        ans = max(ans, L + cur + comp[i]);
        cur = max(max(cur, comp[i]), min(cur, comp[i]) + 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