oj.uz

Submission #286008

# Submission time Handle Problem Language Result Execution time Memory
286008 2020-08-29T22:32:36 Z cjoa Dreaming (IOI13_dreaming) C++11
0 / 100
 1000 ms 17580 KB 
#include "dreaming.h"

#include <vector>
#include <iostream>
#include <queue>
#include <cassert>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

struct Edge {
   int from, to, len;
};

#define MAXN 100004
int NN;
vector<Edge> adj[MAXN];   // graph in adjacency list representation

void dfs(VI& visited, VI& comp, int u) {
   comp.push_back(u);
   visited[u] = true;
   for (Edge e : adj[u]) {
      if (visited[e.to]) continue;
      dfs(visited, comp, e.to);
   }
}

const int INF = 2000000010;
int get_longest_path() {
   int res = 0;
   for (int src = 0; src < NN; ++src) {
      queue<int> q;
      q.push(src);
      VI D(NN, INF);
      D[src] = 0;
      while (!q.empty()) {
         int u = q.front();
         q.pop();
         for (Edge e : adj[u]) {
            if (D[e.to] >= INF) {
               D[e.to] = D[u] + e.len;
               q.push(e.to);
            }
         }
      }

      int max_dist = 0;
      for (int v = 0; v < NN; ++v)
         max_dist = max(max_dist, D[v]);
      res = max(res, max_dist);
   }
   return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
   ::NN = N;

   if ( N >= MAXN )
      return rand();

   for (int j = 0; j < M; ++j) {
      int u = A[j], v = B[j], len = T[j];
      adj[u].push_back({u, v, len});
      adj[v].push_back({v, u, len});
   }

   VVI components;

   VI visited(N, false);
   for (int u = 0; u < N; ++u) {
      if (!visited[u]) {
         VI comp;
         dfs(visited, comp, u);
      // for (int x : comp)
      //    cerr << x << ' ';
      // cerr << endl;
         components.push_back(comp);
      }
   }

   if ( components.size() > 2 )
      assert(false);

   assert( components.size() == 2 );

   VI& comp1 = components[0];
   VI& comp2 = components[1];

   int best_len = INF;
   for (int u : comp1) {
      for (int v : comp2) {
         adj[u].push_back({ u, v, L });
         adj[v].push_back({ v, u, L });

         int len = get_longest_path();
         best_len = min(best_len, len);
         
      // cerr << "Agregando edge " << u << "-> " << v
      //      << " longest path es " << len << endl;

         adj[u].pop_back();
         adj[v].pop_back();
      }
   }

   return best_len;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 10996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 10996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 10996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 17580 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 10996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 10996 KB Time limit exceeded
2 Halted 0 ms 0 KB -