Submission #492097

#	Time	Username	Problem	Language	Result	Execution time	Memory
492097		collodel	Dreaming (IOI13_dreaming)	C++17	100 / 100	88 ms	8992 KiB

dreaming

#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>

#include <iostream>
#include <cassert>
#include <bitset>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>

#pragma optimize("O3")

using namespace std;

// template<typename T>
// using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// template<typename T, typename S>
// using ordered_map = __gnu_pbds::tree<T, S, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template<typename T, typename S>
ostream& operator<< (ostream& out, pair<T, S> p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

// any ct except std::string
template<typename Container,
    typename S = typename enable_if<!is_same<Container, string>::value, typename Container::value_type>::type>
ostream& operator<<(ostream& __out, Container &__ct) {
    __out << "{";
    bool first = true;
    for(auto&& __el : __ct) {
        if(!first) __out << ", ";
        __out << __el;
        first = false;
    }
    return __out << "}";
}
// bitset
template<size_t N>
ostream& operator<<(ostream& __out, bitset<N> &__bs) {
    __out << "{";
    for(size_t i = 0; i < N; ++i) __out << (i != 0 ? ", " : "") /*<< boolalpha*/ << __bs[N - i - 1];
    return __out << "}";
}
template<typename Tail> 
void _dbg(Tail T) {
    cerr << T << '\n';
}
template<typename Head, typename... Tail>
void _dbg(Head H, Tail... T) {
    cerr << H << ", ";
    _dbg(T...);
}

#ifdef DEBUG
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: "; _dbg(__VA_ARGS__);
#else
#define dbg(...) 42
#endif

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    vector<vii> AL(N, vii());

    for(int i = 0; i < M; ++i) {
        AL[A[i]].emplace_back(B[i], T[i]);
        AL[B[i]].emplace_back(A[i], T[i]);
    }

    vi sizes;
    sizes.reserve(N);
    vi diametri;
    diametri.reserve(N);
    vi dist_fw(N, -1);
    vi dist_bw(N, -1);

    // calcola le distanze dei cc
    for(int start = 0; start < N; ++start) {
        // non visitato
        if(dist_fw[start] == -1) {
            // calcola longest path, ricalcolala, prova tutti i nodi in mezzo alla strada piu' lunga

            // parti da u
            queue<int> q;
            dist_fw[start] = 0;
            q.emplace(start);

            int furthest = start;
            int furthest_dist = 0;

            while(!q.empty()) {
                int u = q.front(); q.pop();

                for(auto &[v, w] : AL[u]) {
                    if(dist_fw[v] == -1) {
                        dist_fw[v] = dist_fw[u] + w; // una sola strada possibile
                        q.emplace(v);

                        if(dist_fw[v] > furthest_dist) {
                            furthest = v;
                            furthest_dist = dist_fw[v];
                        }
                    }
                }
            }
    
            // rigira la bfs partendo dal piu' distante
            dist_bw.clear();
            dist_bw[furthest] = 0;
            q.emplace(furthest);

            int end = furthest;
            int end_dist = 0;

            while(!q.empty()) {
                int u = q.front(); q.pop();

                for(auto &[v, w] : AL[u]) {
                    if(dist_bw[v] == -1) {
                        dist_bw[v] = dist_bw[u] + w; // una sola strada possibile
                        q.emplace(v);

                        if(dist_bw[v] > end_dist) {
                            end = v;
                            end_dist = dist_bw[v];
                        }
                    }
                }
            }

            dbg(furthest, end); // diametro

            int to = end;

            // percorri tutti i nodi tra start ed end, trova il migliore
            int best = dist_bw[to];

            while(furthest != to) {
                // avvicinati ad end
                dbg(to);

                int next = AL[to][0].first;
                int next_dist = dist_bw[next];

                for(auto &[v, w] : AL[to]) {
                    if(dist_bw[v] < next_dist) {
                        next = v;
                        next_dist = dist_bw[v];
                    }
                }

                to = next;

                best = min(best, max(dist_bw[to], dist_bw[end] - dist_bw[to]));
            }

            diametri.push_back(dist_bw[end]);
            sizes.push_back(best);
        }
    }

    dbg(diametri, sizes);

    if(sizes.size() == 1) {
        return diametri[0];
    }
    else {
        nth_element(sizes.begin(), sizes.end()-1-0, sizes.end());
        int first = *(sizes.end()-1-0);
        nth_element(sizes.begin(), sizes.end()-1-1, sizes.end());
        int second = *(sizes.end()-1-1);

        int ans = max(
            *max_element(diametri.begin(), diametri.end()),
            first + L + second
        );

        if(sizes.size() == 2) return ans;

        nth_element(sizes.begin(), sizes.end()-1-2, sizes.end());
        int third = *(sizes.end()-1-2);

        return max(ans, second + third + 2 * L);
    }
}

Compilation message (stderr)

dreaming.cpp:13: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
   13 | #pragma optimize("O3")
      | 
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:60:18: warning: statement has no effect [-Wunused-value]
   60 | #define dbg(...) 42
      |                  ^~
dreaming.cpp:137:13: note: in expansion of macro 'dbg'
  137 |             dbg(furthest, end); // diametro
      |             ^~~
dreaming.cpp:60:18: warning: statement has no effect [-Wunused-value]
   60 | #define dbg(...) 42
      |                  ^~
dreaming.cpp:146:17: note: in expansion of macro 'dbg'
  146 |                 dbg(to);
      |                 ^~~
dreaming.cpp:60:18: warning: statement has no effect [-Wunused-value]
   60 | #define dbg(...) 42
      |                  ^~
dreaming.cpp:168:5: note: in expansion of macro 'dbg'
  168 |     dbg(diametri, sizes);
      |     ^~~

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