Submission #1233128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233128		12baater	Dreaming (IOI13_dreaming)	C++20	0 / 100	30 ms	12096 KiB

dreaming

#include "dreaming.h"
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100010;

int link[MAXN];
int size[MAXN];
int longest[MAXN];
int longestChild[MAXN];
int secondLongest[MAXN];
int secondLongestChild[MAXN];
bool visited[MAXN];


vector<pair<int,int>> ADJ[MAXN];


int dfs(int node, int parent) {
    visited[node] = true;
    for (auto [child, w] : ADJ[node]) {
        if (child == parent) continue;
        int ln = dfs(child, node) + w;
        if (ln > secondLongest[node]) {
            secondLongest[node] = ln;
            secondLongestChild[node] = child;
            if (secondLongest[node] > longest[node]) {
                swap(secondLongest[node], longest[node]);
                swap(secondLongestChild[node], longestChild[node]);
            }
        }
    }
    return longest[node];
}


int min_max_dfs(int node, int parent, int other) {
    if (ADJ[node].size() == 0) return 0;
    int best = 2000000000;
    for (auto [child, w] : ADJ[node]) {
        if (child == parent) continue;
        if (child != longestChild[node]) {
            best = min(best, min_max_dfs(child, node, max(other,longest[node]) + w));
        } else {
            best = min(best, min_max_dfs(child, node, max(other, secondLongest[node]) + w));
        }
    }
    // cout << "\n" << node << " " << other << " " << longest[node] << "\n\n";
    return min(best, max(other,longest[node]));
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        ADJ[A[i]].emplace_back(B[i],T[i]);
        ADJ[B[i]].emplace_back(A[i],T[i]);
    }
    priority_queue<int> pq;
    pq.push(0);
    pq.push(0);
    for (int i = 0; i < N; i++) {
        if (visited[i]) continue;
        dfs(i, i);
        pq.push(min_max_dfs(i, i, 0));
        // cout << i << " " << pq.top() << "\n";
        // cout << longest[i] << " " << secondLongest[i] << "\n";
    }
    if (M == N-1) {
        return pq.top();
    }
    int a = pq.top();
    pq.pop();
    int b = pq.top();
    pq.pop();
    return a+b+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