Submission #492092

#	Time	Username	Problem	Language	Result	Execution time	Memory
492092		collodel	Dreaming (IOI13_dreaming)	C++17	77 / 100	1091 ms	12652 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 visited(N, -1);
    vi sizes;
    vi diametri;
    unordered_map<int, int> dist;

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

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

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

                for(auto &[v, w] : AL[u]) {
                    if(dist.find(v) == dist.end()) {
                        dist[v] = dist[u] + w; // una sola strada possibile
                        visited[v] = true;
                        q.emplace(v);
                    }
                }
            }

            int furthest = max_element(dist.begin(), dist.end(), [](const ii &a, const ii &b){
                if(a.second == b.second) {
                    return a.first < b.first;
                }
                return a.second < b.second;
            })->first; // trova l'elemento piu' distante

            // rigira la bfs partendo dal piu' distante
            dist.clear();
            dist[furthest] = 0;
            q.emplace(furthest);

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

                for(auto &[v, w] : AL[u]) {
                    if(dist.find(v) == dist.end()) {
                        dist[v] = dist[u] + w; // una sola strada possibile
                        q.emplace(v);
                    }
                }
            }

            int end = max_element(dist.begin(), dist.end(), [](const ii &a, const ii &b){
                if(a.second == b.second) {
                    return a.first < b.first;
                }
                return a.second < b.second;
            })->first; // trova l'elemento piu' distante

            int to = end;

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

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

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

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

                to = next;

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

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

    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:143:17: note: in expansion of macro 'dbg'
  143 |                 dbg(to);
      |                 ^~~
dreaming.cpp:60:18: warning: statement has no effect [-Wunused-value]
   60 | #define dbg(...) 42
      |                  ^~
dreaming.cpp:159:13: note: in expansion of macro 'dbg'
  159 |             dbg(to);
      |             ^~~

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