Submission #544312

#	Time	Username	Problem	Language	Result	Execution time	Memory
544312		Jomnoi	Dreaming (IOI13_dreaming)	C++17	100 / 100	73 ms	17940 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int MAX = 1e5 + 10;

int ans;
vector <pair <int, int>> adj[MAX];
pair <int, int> ma[MAX][2];
bool visited[MAX];

template <typename T>
void upd(T *ma, T x, int n) {
    for(int i = 0; i < n; i++) {
        if(ma[i] < x) {
            swap(ma[i], x);
        }
    }
}

void dfs(int u) {
    for(auto [v, w] : adj[u]) {
        if(visited[v] == true) {
            continue;
        }
        visited[v] = true;

        dfs(v);
        upd(ma[u], make_pair(ma[v][0].first + w, v), 2);
    }
    ans = max(ans, ma[u][0].first + ma[u][1].first);
}

int dfs2(int u, int pw) {
    int res = max(ma[u][0].first, pw);
    for(auto [v, w] : adj[u]) {
        if(visited[v] == true) {
            continue;
        }
        visited[v] = true;

        int nw = pw;
        if(ma[u][0].second == v) {
            nw = max(nw, ma[u][1].first);
        }
        else {
            nw = max(nw, ma[u][0].first);
        }

        res = min(res, dfs2(v, nw + w));
    }
    return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++) {
        A[i]++, B[i]++;
        adj[A[i]].emplace_back(B[i], T[i]);
        adj[B[i]].emplace_back(A[i], T[i]);
    }

    for(int i = 1; i <= N; i++) {
        ma[i][0] = make_pair(0, -1);
        ma[i][1] = make_pair(0, -1);
    }
    for(int i = 1; i <= N; i++) {
        if(visited[i] == false) {
            visited[i] = true;
            dfs(i);
        }
    }

    for(int i = 1; i <= N; i++) {
        visited[i] = false;
    }
    
    vector <int> max_dist;
    for(int i = 1; i <= N; i++) {
        if(visited[i] == false) {
            visited[i] = true;
            max_dist.push_back(dfs2(i, 0));
        }
    }

    sort(max_dist.rbegin(), max_dist.rend());
    if(max_dist.size() > 1) {
        ans = max(ans, max_dist[0] + max_dist[1] + L);
    }
    if(max_dist.size() > 2) {
        ans = max(ans, max_dist[1] + max_dist[2] + 2 * 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