Submission #286973

#	Time	Username	Problem	Language	Result	Execution time	Memory
286973		themax23	꿈 (IOI13_dreaming)	C++17	100 / 100	273 ms	25476 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define deb(x) cerr << #x <<": " << x << '\n';
using namespace std;

typedef vector<int> VI;
typedef pair<int,int> II;
const int INF  = 1000000010;


struct Edge {
	int to, weight;
};


typedef vector< vector<Edge> > Graph;
int N;
Graph billabongs;
vector<bool> vis;
VI component;

void dfs1(int src){
	vis[src] = true;
	component.push_back(src);
	for(Edge e : billabongs[src]){
		if(vis[e.to]) continue;
		dfs1(e.to);
	}
}

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.weight);
   }
}

II get_center_points(const Graph& tree) {
   const int n = tree.size();
   if (n == 1)
      return {0, 0};
//Longest path in a tree
// 	finding first endpoint of the tree
	VI D1(n,-1);
	int u_max = 0;
	dfs2(tree,D1,0);
	for(int u = 0; u < n; ++u) {
	if (D1[u] > D1[u_max])
		u_max = u;
   }
	//deb(u_max);
//	finding the second endpoint of the tree
	VI D2(n,-1);
	int v_max = 0;
	dfs2(tree,D2,u_max);
	for(int v = 0; v < n; ++v) {
		if (D2[v] > D2[v_max])
			v_max = v;
   }
	//deb(v_max);
//	filling the Distances for the second endpoint
	VI D3(n,-1);
	dfs2(tree,D3,v_max);
// 	finding the "center point"
	II best = {INF,INF}, temp;
	for(int u = 0; u < n; ++u){
		if(D2[u] > D3[u])
			temp = {D2[u], D3[u]};
		else
			temp = {D3[u], D2[u]};
		best = min(best,temp);
	}
	return best;
}


Graph renumerate(){
	map<int,int> new_id;
	int n = (int) component.size();
	for(int i = 0; i < n; ++i)
		new_id[component[i]] = i;
	Graph tree(n);
	for(int u : component){
		int new_id_of_u = new_id[u];
		for(Edge e : billabongs[u]){
			int new_id_of_v = new_id[e.to];
			tree[new_id_of_u].push_back({new_id_of_v, e.weight});
			//tree[new_id_of_v].push_back({new_id_of_u, e.weight}); not added because it was previously 
			//													    added when extracting the Graph (line 104)
		}
	}
	return tree;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	::N = N;
	//First part representing the Graph
	billabongs = Graph(N);
	for(int i = 0; i < M; ++i){
		int u = A[i], v = B[i], weight = T[i];
		billabongs[u].push_back({v,weight});
		billabongs[v].push_back({u,weight});
	}
	vis = vector<bool>(N,false);
	vector<Graph> trees;
	//Second part getting the connected components (trees)
	for(int i = 0; i < N; ++i){
		if(vis[i]) continue;
		component = VI(0);
		dfs1(i);
	//Third part renumerating the ids of the nodes of the trees
		Graph tree = renumerate();
		trees.emplace_back(tree);
	}
	//for testing
	/*
	int comp = 0;
	for(Graph tree : trees){
			cerr << "component # " << comp++ << '\n';
			for(int j = 0; j < (int)tree.size(); ++j){
			cerr << "Node: " << j << '\n';
			for(Edge e : tree[j]){
				cerr << "e.to: " << e.to << " e.weight: " << e.weight << '\n';
			}
		}
	}
	*/
	//Fourth part getting the center points of the trees
	vector<II> center_points;
	for(Graph tree : trees){
		II center_point = get_center_points(tree);
		//cerr <<"center_point: " << center_point.first << ' ' << center_point.second << '\n';
		center_points.push_back(center_point);
	}
	sort(center_points.begin(), center_points.end(), greater<II>());
	int ans = 0;
	 //checking if the longest path is on the current tree;
	for (II center_point : center_points)
		ans = max(ans, center_point.first + center_point.second);
	//checking if there are 2 or more center points
	if (int(center_points.size()) > 1) {		
		ans = max(ans,center_points[0].first + L + center_points[1].first);
	for (int i = 2; i < int(center_points.size()); ++i) {
		ans = max(ans, center_points[i].first + 2*L + center_points[1].first);
      }
   }
    return ans;
}

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