Submission #372471

#	Time	Username	Problem	Language	Result	Execution time	Memory
372471		two_sides	Dreaming (IOI13_dreaming)	C++17	100 / 100	117 ms	10220 KiB

dreaming

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

using namespace std;

const int N = 100005;

vector <pair <int, int>> adj[N];
int par[N], dis[N];
queue <int> que;

void BFS(int u, int &diam, int &dist) {
    int far = u; diam = 0;
    que.push(u); dis[u] = 0; par[u] = -1;
    while (que.size()) {
        u = que.front(); que.pop();
        if (dis[u] > diam) {
            diam = dis[u]; far = u;
        }
        for (auto e : adj[u]) {
            int v, w; tie(v, w) = e;
            if (v != par[u]) {
                dis[v] = dis[u] + w;
                par[v] = u; que.push(v);
            }
        }
    }
    que.push(u = far);
    diam = dis[u] = 0; par[u] = -1;
    while (que.size()) {
        u = que.front(); que.pop();
        if (dis[u] > diam) {
            diam = dis[u]; far = u;
        }
        for (auto e : adj[u]) {
            int v, w; tie(v, w) = e;
            if (v != par[u]) {
                dis[v] = dis[u] + w;
                par[v] = u; que.push(v);
            }
        }
    }
    dist = INT_MAX; u = far;
    while (u >= 0) {
        dist = min(dist, max
        (dis[u], dis[far] - dis[u]));
        u = par[u];
    }
    
}

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]);
    }
    memset(dis, -1, sizeof dis);
    vector <int> tmp; int res = 0;
    for (int i = 0; i < n; i++)
        if (dis[i] < 0) {
            int diam, dist;
            BFS(i, diam, dist);
            res = max(res, diam);
            tmp.push_back(dist);
        }
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i + 1 < n - m; i++)
        tmp[i] += l;
    sort(tmp.begin(), tmp.end());
    if (n - m > 1)
        res = max(res,
        tmp[n - m - 1] + tmp[n - m - 2]);
    return res;
}

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