Submission #286007

#	Time	Username	Problem	Language	Result	Execution time	Memory
286007		cjoa	Dreaming (IOI13_dreaming)	C++11	0 / 100	33 ms	1532 KiB

dreaming

#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 104
int N;
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 < N; ++src) {
      queue<int> q;
      q.push(src);
      VI D(N, 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 < N; ++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[]) {
   ::N = 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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23