Submission #991917

#	Time	Username	Problem	Language	Result	Execution time	Memory
991917		phoenix	Dreaming (IOI13_dreaming)	C++17	100 / 100	48 ms	17148 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));
        }
    }
    auto merge = [&](pair<int, int> t1, pair<int, int> t2) -> pair<int, int> {
        if (t1.first + t1.second < t2.first + t2.second)
            swap(t1, t2);
        if (t1.first + t1.second >= t1.first + t2.first + L)
            return t1;
        t1.first += L;
        t1.second = t2.first;
        if (t1.first > t1.second + L) {
            t1.first -= L;
            t1.second += L;
        }
        if (t1.first < t1.second)
            swap(t1.first, t1.second);
        return t1;
    };

    sort(br.begin(), br.end());
    // for (auto c : br) {
    //     cout << '(' << c.first << ' ' << c.second << ')' << ' ';
    // }
    // cout << '\n';

    for (int i = 0; i < (int)br.size() - 1; i++) {
        br.back() = merge(br.back(), br[i]);
    }
    return br.back().first + br.back().second;
}

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