Submission #573875

#	Time	Username	Problem	Language	Result	Execution time	Memory
573875		MohamedFaresNebili	Dreaming (IOI13_dreaming)	C++14	100 / 100	103 ms	18688 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        const int oo = 1e18 + 7;

        int K, res, par[100001], E[100001];
        int D[100001], D1[100001];
        vector<ii> adj[100001];
        vector<int> S;
        bool vis[100001];
        int findSet(int v) {
            if(par[v] == v) return v;
            return par[v] = findSet(par[v]);
        }
        void unionSet(int u, int v, int L) {
            u = findSet(u); v = findSet(v);
            if(u == v) return;
            if(max(E[u], E[v] + L) > max(E[v], E[u] + L)) swap(u, v);
            res = max(res, E[u] + E[v] + L);
            E[u] = max(E[u], E[v] + L);
            par[v] = u;
        }
        void dfs(int v, int p, int dep) {
            D[v] = dep; S.pb(v);
            for(auto u : adj[v]) {
                if(u.ff == p) continue;
                dfs(u.ff, v, dep + u.ss);
            }
        }
        void dfs(int v, int p, int dep, int d) {
            if(d == 0) D[v] = dep;
            if(d == 1) D1[v] = dep;
            for(auto u : adj[v]) {
                if(u.ff == p) continue;
                dfs(u.ff, v, dep + u.ss, d);
            }
        }
        bool cmp(int u, int v) {
            return max(E[u], E[v] + K) < max(E[v], E[u] + K);
        }

        int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
            for(int l = 0; l < N; l++) par[l] = l;
            for(int l = 0; l < M; l++) {
                int U = A[l], V = B[l], W = T[l];
                adj[U].pb({V, W}), adj[V].pb({U, W});
            }
            vector<int> reys; K = L;
            for(int l = 0; l < N; l++) {
                if(vis[l]) continue;
                dfs(l, l, 0); int p = l;
                for(auto u : S) {
                    if(D[u] <= D[p]) continue;
                    p = u;
                }
                dfs(p, p, 0, 0); int to = p;
                for(auto u : S) {
                    if(D[u] <= D[to]) continue;
                    to = u; res = max(res, D[u]);
                }
                dfs(to, to, 0, 1);
                int med = p, curr = 1e9 + 7;
                for(auto u : S) {
                    if(D[u] + D1[u] == D[to]) {
                        if(max(D[u], D1[u]) < curr)
                            med = u, curr = max(D[u], D1[u]);
                    }
                }
                for(auto u : S) par[u] = med, vis[u] = 1;
                E[med] = curr; S.clear(); reys.pb(med);
            }
            sort(reys.begin(), reys.end(), cmp);
            for(int l = 1; l < (int)reys.size(); l++)
                unionSet(reys[0], reys[l], L);
            return res;
        }

Compilation message (stderr)

dreaming.cpp:21:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 |         const int oo = 1e18 + 7;
      |                        ~~~~~^~~

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