제출 #1276855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276855		tredsused70	꿈 (IOI13_dreaming)	C++20	100 / 100	46 ms	18908 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

const int nmax = 100000;

vector<array<int, 2>> graf[nmax];
int ans, cur;
int used[nmax], dist_down[nmax], dist_up[nmax];

void dfs_down(int v, int p = -1) {
    used[v] = 1;
    dist_down[v] = 0;
    for(auto i : graf[v]) {
        if(i[0] == p)
            continue;
        dfs_down(i[0], v);
        dist_down[v] = max(dist_down[v], dist_down[i[0]] + i[1]);
    }
    return ;
}

void dfs_total(int v, int p = -1) {
    array<int, 2> maximum[2];
    maximum[0] = {-1, -1};
    maximum[1] = {-1, -1};
    for(auto i : graf[v]) {
        if(i[0] == p)
            continue;
        int cur_dist = dist_down[i[0]] + i[1];
        if(cur_dist > maximum[0][0]) {
            maximum[1] = maximum[0];
            maximum[0][0] = cur_dist;
            maximum[0][1] = i[0];
        }
        else {
            if(cur_dist > maximum[1][0]) {
                maximum[1][0] = cur_dist;
                maximum[1][1] = i[0];
            }
        }
    }
    cur = min(cur, max(dist_up[v], maximum[0][0]));
    ans = max(ans, max(maximum[0][0], 0) + max(maximum[1][0], 0));
    for(auto i : graf[v]) {
        if(i[0] == p)
            continue;
        dist_up[i[0]] = dist_up[v] + i[1];
        if(i[0] == maximum[0][1])
            dist_up[i[0]] = max(dist_up[i[0]], maximum[1][0] + i[1]);
        else
            dist_up[i[0]] = max(dist_up[i[0]], maximum[0][0] + i[1]);
        dfs_total(i[0], v);
    }
    return ;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    ans = 0;
    for(int i = 0; i < m; i++) {
        graf[a[i]].push_back({b[i], t[i]});
        graf[b[i]].push_back({a[i], t[i]});
    }
    fill(used, used + n, 0);
    fill(dist_down, dist_down + n, 0);
    fill(dist_up, dist_up + n, 0);
    vector<int> components;
    for(int i = 0; i < n; i++) {
        if(!used[i]) {
            cur = 1000000010;
            dfs_down(i);
            dist_up[i] = 0;
            dfs_total(i);
            components.push_back(cur);
        }
    }
    sort(components.begin(), components.end());
    reverse(components.begin(), components.end());
    if(components.size() > 1)
        ans = max(ans, components[0] + l + components[1]);
    if(components.size() > 2)
        ans = max(ans, components[1] + l + l + components[2]);
    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