Submission #759325

#	Time	Username	Problem	Language	Result	Execution time	Memory
759325		lukameladze	Dreaming (IOI13_dreaming)	C++17	100 / 100	61 ms	23448 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int inf = 1e9, N = 3e5 + 5;
vector <pii> v[N];
int lv[2][N], fix[N], cur_mx, vert, diam, rad, ans, a[N], b[N], c[N];
void dfs(int a, int p, int ty) {
    fix[a] = 1;
    if (lv[ty][a] > cur_mx) cur_mx = lv[ty][a], vert = a;
    if (ty == 1) rad = min(rad, max(lv[ty][a], diam - lv[ty][a]));
    for (pii sth : v[a]) {
        int to = sth.f, c = sth.s;
        if (to == p) continue;
        if (ty == 1 && lv[0][to] != lv[0][a] - c) continue;
        lv[ty][to] = lv[ty][a] + c;
        dfs(to, a, ty);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int n = N, m = M, l = L;
    vector <int> vec;
    for (int i = 0; i < m; i++) {
        a[i] = A[i] + 1; b[i] = B[i] + 1; c[i] = T[i];
        v[a[i]].pb({b[i], c[i]});
        v[b[i]].pb({a[i], c[i]});
    }
    for (int i = 1; i <= n; i++) {
        if (!fix[i]) { diam = 0;
            cur_mx = -1; lv[0][i] = 0; dfs(i, 0, 0);
            cur_mx = -1; lv[0][vert] = 0;  dfs(vert, 0, 0); diam = cur_mx; ans = max(ans, diam);
            cur_mx = -1; lv[1][vert] = 0; rad = inf; dfs(vert, 0, 1);
            vec.pb(rad);
        }
    }
    sort(vec.rbegin(), vec.rend());
    if (vec.size() > 1) ans = max(ans, vec[0] + vec[1] + l);
    if (vec.size() > 2) ans = max(ans, 2 * l + vec[1] + vec[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