Submission #285441

#	Time	Username	Problem	Language	Result	Execution time	Memory
285441		cjoa	Dreaming (IOI13_dreaming)	C++11	100 / 100	311 ms	28588 KiB

dreaming

#include "dreaming.h"
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cstdlib>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> II;
typedef long long llong;

const int INF = 2e9;

struct Edge {
   int to, len;
};

typedef vector< vector<Edge> > Graph;

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

void dfs1(const Graph& G, vector<bool>& vis, VI& comp, int u) {
   vis[u] = true;
   comp.push_back(u);
   for (Edge e : G[u]) {
      if (vis[e.to]) continue;
      dfs1(G, vis, comp, e.to);
   }
}

Graph renumerate(const Graph& G, const VI& comp) {
   map<int,int> new_id;
   for (int u : comp) {
      int id = new_id.size();
      new_id[u] = id;
   }

   Graph new_graph(comp.size());
   for (int u : comp) {
      int uid = new_id[u];
      for (Edge e : G[u]) {
         assert( new_id.count(e.to) );
         int vid = new_id[e.to];
         new_graph[uid].push_back({vid, e.len});
      }
   }
   return new_graph;
}

void dfs2(const Graph& tree, VI& D, int u, int d = 0) {
   D[u] = d;
   for (Edge e : tree[u]) {
      if (D[e.to] >= 0) continue;
      dfs2(tree, D, e.to, d+e.len);
   }
}

II get_center_distances(const Graph& tree) {
   const int N = tree.size();
   if (N == 1)
      return {0, 0};

   VI D(N, -1);
   dfs2(tree, D, 0);
   int u_max = 0;
   for (int u = 0; u < N; ++u) {
      if (D[u] > D[u_max])
         u_max = u;
   }

   VI D1(N, -1);
   dfs2(tree, D1, u_max);
   int v_max = 0;
   for (int v = 0; v < N; ++v) {
      if (D1[v] > D1[v_max])
         v_max = v;
   }
   
   VI D2(N, -1);
   dfs2(tree, D2, v_max);

   II best(INF, INF);
   for (int u = 0; u < N; ++u) {
      II cur(D1[u], D2[u]);
      if (cur.first < cur.second)
         swap(cur.first, cur.second);
      best = min(best, cur);
   }

   return best;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
   vector< vector<Edge> > G = extract_graph(N, M, A, B, T);

   vector<Graph> trees;

   vector<bool> vis(N, false);
   for (int u = 0; u < N; ++u) {
      if (!vis[u]) {
         VI comp;
         dfs1(G, vis, comp, u);
         Graph C = renumerate(G, comp);
         trees.emplace_back(C);
      }
   }

   vector<II> center_distances;
   for (Graph t : trees) {
      II cd = get_center_distances(t);
      center_distances.push_back(cd);
   // cerr << cd.first << ',' << cd.second << endl;
   }

   sort(center_distances.begin(), center_distances.end(), greater<II>());

   int res = 0;
   for (II cd : center_distances)
      res = max(res, cd.first + cd.second);

   if (int(center_distances.size()) > 1) {
      res = max(res,
                center_distances[0].first + L + center_distances[1].first);

      for (int j = 2; j < int(center_distances.size()); ++j) {
         res = max(res,
                   center_distances[j].first + 2*L + center_distances[1].first);
      }
   }

   return res;
}

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