Submission #993434

#	Time	Username	Problem	Language	Result	Execution time	Memory
993434		Alfraganus	Dreaming (IOI13_dreaming)	C++17	47 / 100	110 ms	8792 KiB

dreaming

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

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    vector<vector<array<int, 2>>> graph(n);
    for(int i = 0; i < m; i ++)
        graph[a[i]].push_back({b[i], t[i]}), graph[b[i]].push_back({a[i], t[i]});
    vector<int> d;
    vector<array<int, 2>> lnk(n, {-1, -1});
    vector<bool> used(n);
    int res = 0;
    for(int i = 0; i < n; i ++){
        if(!used[i]){
            set<array<int, 2>> st;
            st.insert({0, i});
            used[i] = 1;
            int last = -1;
            while(!st.empty()){
                auto [x, y] = *st.begin();
                st.erase(st.begin());
                last = y;

                for(auto z : graph[y]){
                    if(!used[z[0]]){
                        st.insert({x + z[1], z[0]});
                        used[z[0]] = 1;
                    }
                }
            }
            used[last] = 0;
            st.insert({0, last});
            while(!st.empty()){
                auto [x, y] = *st.begin();
                st.erase(st.begin());
                last = y;

                for(auto z : graph[y]){
                    if(used[z[0]]){
                        lnk[z[0]] = {y, z[1]};
                        st.insert({x + z[1], z[0]});
                        used[z[0]] = 0;
                    }
                }
            }
            used[i] = 1;
            st.insert({0, i});

            while(!st.empty()){
                auto [x, y] = *st.begin();
                st.erase(st.begin());
                
                for(auto z : graph[y]){
                    if(!used[z[0]]){
                        st.insert({x + z[1], z[0]});
                        used[z[0]] = 1;
                    }
                }
            }
            vector<int> p;
            int sum = 0;
            while(lnk[last][0] != -1){
                p.push_back(lnk[last][1]);
                sum += p.back();
                last = lnk[last][0];
            }
            res = max(res, sum);
            p.push_back(0);
            int ans = 1e9, s = 0;
            for(int i = 0; i < (int)p.size(); i ++)
                ans = min(ans, max(s, sum - s)), s += p[i];
            d.push_back(ans);
        }
    }
    if(d.size() == 1)
        return res;
    else if(d.size() == 2)
        return max(res, d[0] + d[1] + l);
    else{
        sort(d.begin(), d.end());
        int ans = res;
        int k = d.size();
        for(int i = 0; i < k - 2; i ++)
            ans = min(ans, max({res, d[k - 2] + d[k - 1] + 2 * l, d[i] + l + d[k - 1]}));
        ans = min(ans, max({res, d[k - 2] + d[k - 1] + l, d[k - 1] + d[k - 3] + 2 * l}));
        ans = min(ans, max({res, d[k - 2] + d[k - 1] + l, d[k - 2] + d[k - 3] + 2 * l}));
        return ans;
    }
}

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