Submission #142754

#	Time	Username	Problem	Language	Result	Execution time	Memory
142754		socho	Dreaming (IOI13_dreaming)	C++14	100 / 100	163 ms	18200 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

const int MX = 100005;

vector<pair<int, int> > adj[MX];
vector<int> subtrees;
bool visited[MX];

void dfs_visit(int node, int last) {
	visited[node] = true;
	for (int i=0; i<adj[node].size(); i++) {
		int other = adj[node][i].first;
		if (other != last) {
			dfs_visit(other, node);
		}
	}
}

int distance_[MX];
vector<int> subtree_contents;

void dfs_get(int node, int last, int dist) {
	distance_[node] = dist;
	subtree_contents.push_back(node);
	for (int i=0; i<adj[node].size(); i++) {
		int other = adj[node][i].first;
		int distto = adj[node][i].second;
		if (other != last) {
			dfs_get(other, node, dist+distto);
		}
	}
}

bool found = false;
bool opennodes[MX];

void dfs_find(int node, int last, int dist, int toget) {
	opennodes[node] = true;
	
	if (dist == toget) {
		found = true;
	}
	
	for (int i=0; i<adj[node].size(); i++) {
		if (found) continue;
		int other = adj[node][i].first;
		int distto = adj[node][i].second;
		if (other != last) {
			dfs_find(other, node, dist+distto, toget);
		}
	}
	
	if (!found) opennodes[node] = false;
}

pair<int, int> solve_subtree(int num) { // get mxdist out, center
	int subtr = subtrees[num];
	subtree_contents.clear();
	dfs_get(subtr, -1, 0);
	int farnode = -1;
	int fardist = -1;
	for (int i=0; i<subtree_contents.size(); i++) {
		int nd = subtree_contents[i];
		int distat = distance_[nd];
		if (distat > fardist) {
			fardist = distat;
			farnode = nd;
		}
	}
	subtree_contents.clear();
	dfs_get(farnode, -1, 0);
	fardist = 0;
	for (int i=0; i<subtree_contents.size(); i++) {
		int nd = subtree_contents[i];
		int distat = distance_[nd];
		if (distat > fardist) {
			fardist = distat;
			farnode = nd;
		}
	}
	
	found = false;
	dfs_find(farnode, -1, 0, fardist);
	
	int lowest_difference = fardist;
	int lowest_node = farnode;
	
	for (int i=0; i<subtree_contents.size(); i++) {
		int nd = subtree_contents[i];
		if (opennodes[nd]) {
			int a = fardist - distance_[nd];
			int b = distance_[nd];
			int dif = abs(a-b);
			if (dif < lowest_difference) {
				lowest_difference = dif;
				lowest_node = nd;
			}
		}
	}
	
	subtree_contents.clear();
	
	int a = fardist - distance_[lowest_node];
	int b = distance_[lowest_node];
	
	return make_pair(max(a, b), lowest_node);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
		
	memset(opennodes, 0, sizeof opennodes);	
		
	for (int i=0; i<M; i++) {
		int a = A[i];
		int b = B[i];
		int t = T[i];
		adj[a].push_back(make_pair(b, t));
		adj[b].push_back(make_pair(a, t));
	}
	
	memset(visited, 0, sizeof visited);
	for (int i=0; i<N; i++) {
		if (!visited[i]) {
			dfs_visit(i, -1);
			subtrees.push_back(i);
		}
	}
	
	vector<pair<int, int> > solves;
	
	for (int i=0; i<subtrees.size(); i++) {
		solves.push_back(solve_subtree(i));
	}
	
	sort(solves.rbegin(), solves.rend());
	
	pair<int, int> cen = solves[0];
	
	for (int i=1; i<solves.size(); i++) {
		// cout << "connect " << cen.second << " to " << solves[i].second << endl;
		int a = cen.second;
		int b = solves[i].second;
		adj[a].push_back(make_pair(b, L));
		adj[b].push_back(make_pair(a, L));
	}
	
	subtree_contents.clear();
	
	dfs_get(0, -1, 0);
	
	int mxdist = 0;
	int mxnode = 0;
	
	for (int i=0; i<N; i++) {
		int dist_to = distance_[i];
		if (dist_to > mxdist) {
			mxdist = dist_to;
			mxnode = i;
		}
	}
	
	dfs_get(mxnode, -1, 0);
	
	mxdist = 0;
	
	for (int i=0; i<N; i++) {
		int dist_to = distance_[i];
		if (dist_to > mxdist) {
			mxdist = dist_to;
			mxnode = i;
		}
	}
	
    return mxdist;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs_visit(int, int)':
dreaming.cpp:13:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs_get(int, int, int)':
dreaming.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs_find(int, int, int, int)':
dreaming.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'std::pair<int, int> solve_subtree(int)':
dreaming.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<subtree_contents.size(); i++) {
                ~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:75:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<subtree_contents.size(); i++) {
                ~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<subtree_contents.size(); i++) {
                ~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:133:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<subtrees.size(); i++) {
                ~^~~~~~~~~~~~~~~~
dreaming.cpp:141:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<solves.size(); i++) {
                ~^~~~~~~~~~~~~~

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