Submission #991937

#	Time	Username	Problem	Language	Result	Execution time	Memory
991937		phoenix	Dreaming (IOI13_dreaming)	C++17	100 / 100	45 ms	16244 KiB

dreaming

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

using namespace std;

const int N = 100100;


vector<pair<int, int>> g[N];
vector<bool> vis;

int nxt[N];
int w[N];

int calc(int s, int p) {
    vis[s] = true;
    int res = 0;
    nxt[s] = s;
    w[s] = 0;
    for (auto [to, wt] : g[s]) if (to != p) {
        int x = calc(to, s);
        if (res < x + wt) {
            res = x + wt;
            nxt[s] = to;
            w[s] = wt;
        }
    }
    return res;
}

pair<int, int> find_center(int s) {
    calc(s, s);
    
    while (nxt[s] != s) s = nxt[s];
    calc(s, s);
    vector<int> arr;
    while (nxt[s] != s) {
        arr.push_back(w[s]);
        s = nxt[s];
    }
    int sum = 0;
    for (int c : arr) sum += c;
    int mn = sum;
    int cur = 0;

    for (int i = 0; i < (int)arr.size(); i++) {
        cur += arr[i];
        if (max(cur, sum - cur) < mn) {
            mn = max(cur, sum - cur);
        }
    }
    pair<int, int> res = {mn, sum - mn};
    if (res.first < res.second)
        swap(res.first, res.second); 
    return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    vis.assign(N, false);
    vector<pair<int, int>> br;
    for (int i = 0; i < N; i++) {
        if (!vis[i]) {
            br.push_back(find_center(i));
        }
    }
    int m = (int)br.size();

    sort(br.begin(), br.end());
    int res = 0;
    for (int i = 0; i < m; i++) 
        res = max(res, br[i].first + br[i].second);

    for (int i = 0; i < m - 1; i++) {
        res = max(res, br[i].first + br[m - 1].first + L);
    }
    if (m >= 3) res = max(res, br[m - 3].first + br[m - 2].first + 2 * L);

    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