143923277f 2014-11-03        kinaba: #include <iostream>
143923277f 2014-11-03        kinaba: #include <sstream>
143923277f 2014-11-03        kinaba: #include <iomanip>
143923277f 2014-11-03        kinaba: #include <vector>
143923277f 2014-11-03        kinaba: #include <string>
143923277f 2014-11-03        kinaba: #include <map>
143923277f 2014-11-03        kinaba: #include <set>
143923277f 2014-11-03        kinaba: #include <algorithm>
143923277f 2014-11-03        kinaba: #include <numeric>
143923277f 2014-11-03        kinaba: #include <iterator>
143923277f 2014-11-03        kinaba: #include <functional>
143923277f 2014-11-03        kinaba: #include <complex>
143923277f 2014-11-03        kinaba: #include <queue>
143923277f 2014-11-03        kinaba: #include <stack>
143923277f 2014-11-03        kinaba: #include <cmath>
143923277f 2014-11-03        kinaba: #include <cassert>
143923277f 2014-11-03        kinaba: #include <tuple>
143923277f 2014-11-03        kinaba: using namespace std;
143923277f 2014-11-03        kinaba: typedef long long LL;
143923277f 2014-11-03        kinaba: typedef complex<double> CMP;
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: const int INF = 0x1fffffff;
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: class CandleTimer { public:
143923277f 2014-11-03        kinaba: 	int differentTime(vector <int> A, vector <int> B, vector <int> len)
143923277f 2014-11-03        kinaba: 	{
143923277f 2014-11-03        kinaba: 		if(A.size() == 1) {
143923277f 2014-11-03        kinaba: 			// Special case, just in case. All nodes are leaves.
143923277f 2014-11-03        kinaba: 			// Either light only one end or both ends.
143923277f 2014-11-03        kinaba: 			return 2;
143923277f 2014-11-03        kinaba: 		}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		// x2, to make all the possible final points on integer coordinates.
143923277f 2014-11-03        kinaba: 		for(auto& li: len)
143923277f 2014-11-03        kinaba: 			li *= 2;
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		// Prepare....
143923277f 2014-11-03        kinaba: 		const int E = A.size(), V = E+1;
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		vector<int> leaf;
143923277f 2014-11-03        kinaba: 		vector<bool> is_leaf(V, false);
143923277f 2014-11-03        kinaba: 		{
143923277f 2014-11-03        kinaba: 			vector<int> degree(V);
143923277f 2014-11-03        kinaba: 			for(auto a: A) degree[a]++;
143923277f 2014-11-03        kinaba: 			for(auto b: B) degree[b]++;
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 			for(int v=0; v<V; ++v)
143923277f 2014-11-03        kinaba: 				if(degree[v]==1) {
143923277f 2014-11-03        kinaba: 					leaf.push_back(v);
143923277f 2014-11-03        kinaba: 					is_leaf[v] = true;
143923277f 2014-11-03        kinaba: 				}
143923277f 2014-11-03        kinaba: 		}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		vector<vector<int>> dist(V, vector<int>(V, INF));
143923277f 2014-11-03        kinaba: 		{
143923277f 2014-11-03        kinaba: 			for(int i=0; i<V; ++i)
143923277f 2014-11-03        kinaba: 				dist[i][i] = 0;
143923277f 2014-11-03        kinaba: 			for(int i=0; i<E; ++i)
143923277f 2014-11-03        kinaba: 				dist[A[i]][B[i]] = dist[B[i]][A[i]] = len[i];
143923277f 2014-11-03        kinaba: 			for(int k=0; k<V; ++k)
143923277f 2014-11-03        kinaba: 			for(int i=0; i<V; ++i)
143923277f 2014-11-03        kinaba: 			for(int j=0; j<V; ++j)
143923277f 2014-11-03        kinaba: 				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
143923277f 2014-11-03        kinaba: 		}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		vector<vector<pair<int,int>>> G(V); // len, dest
143923277f 2014-11-03        kinaba: 		for(int e=0; e<E; ++e) {
143923277f 2014-11-03        kinaba: 			G[A[e]].emplace_back(len[e], B[e]);
143923277f 2014-11-03        kinaba: 			G[B[e]].emplace_back(len[e], A[e]);
143923277f 2014-11-03        kinaba: 		}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		// Compute all possible final points.
143923277f 2014-11-03        kinaba: 		enum {EID, POS};
143923277f 2014-11-03        kinaba: 		vector<tuple<int,int>> cand;
143923277f 2014-11-03        kinaba: 		{
143923277f 2014-11-03        kinaba: 			vector<bool> done(V, false);
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 			// Add all leaves as the possible final point
143923277f 2014-11-03        kinaba: 			for(int e=0; e<E; ++e) {
143923277f 2014-11-03        kinaba: 				if(is_leaf[A[e]] && !done[A[e]])
143923277f 2014-11-03        kinaba: 					cand.emplace_back(e, 0), done[A[e]]=true;
143923277f 2014-11-03        kinaba: 				if(is_leaf[B[e]] && !done[B[e]])
143923277f 2014-11-03        kinaba: 					cand.emplace_back(e, len[e]), done[B[e]]=true;
143923277f 2014-11-03        kinaba: 			}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 			// Add all mid points.
143923277f 2014-11-03        kinaba: 			for(int la: leaf)
143923277f 2014-11-03        kinaba: 			for(int lb: leaf)
143923277f 2014-11-03        kinaba: 			for(int e=0; e<E; ++e)
143923277f 2014-11-03        kinaba: 			{
143923277f 2014-11-03        kinaba: 				int a=A[e], b=B[e], ll=len[e];
143923277f 2014-11-03        kinaba: 				if(dist[la][a]+ll+dist[lb][b] == dist[la][lb]) {
143923277f 2014-11-03        kinaba: 					if(abs(dist[la][a] - dist[lb][b]) <= ll) {
143923277f 2014-11-03        kinaba: 						tuple<int,int> c(e, (ll+dist[lb][b]-dist[la][a])/2);
143923277f 2014-11-03        kinaba: 						// TODO: reduce by done[]
143923277f 2014-11-03        kinaba: 						cand.push_back(c);
143923277f 2014-11-03        kinaba: 					}
143923277f 2014-11-03        kinaba: 				} else if(dist[la][b]+ll+dist[lb][a] == dist[la][lb]) {
143923277f 2014-11-03        kinaba: 					if(abs(dist[la][b] - dist[lb][a]) <= ll) {
143923277f 2014-11-03        kinaba: 						tuple<int,int> c(e, (ll+dist[la][b]-dist[lb][a])/2);
143923277f 2014-11-03        kinaba: 						// TODO: reduce by done[]
143923277f 2014-11-03        kinaba: 						cand.push_back(c);
143923277f 2014-11-03        kinaba: 					}
143923277f 2014-11-03        kinaba: 				}
143923277f 2014-11-03        kinaba: 			}
143923277f 2014-11-03        kinaba: 		}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		// Distance between a candidate point and a node.
143923277f 2014-11-03        kinaba: 		function<int(tuple<int,int>,int)> calc_d = [&](tuple<int,int> c, int v) {
143923277f 2014-11-03        kinaba: 			return min(
143923277f 2014-11-03        kinaba: 				dist[A[get<EID>(c)]][v] + get<POS>(c),
143923277f 2014-11-03        kinaba: 				dist[B[get<EID>(c)]][v] + len[get<EID>(c)] - get<POS>(c)
143923277f 2014-11-03        kinaba: 			);
143923277f 2014-11-03        kinaba: 		};
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		// Simulate all.
143923277f 2014-11-03        kinaba: 		set<int> answer;
143923277f 2014-11-03        kinaba: 		for(auto c: cand)
143923277f 2014-11-03        kinaba: 		{
143923277f 2014-11-03        kinaba: 			vector<pair<int,int>> dist_leaf;
143923277f 2014-11-03        kinaba: 			for(int v: leaf)
143923277f 2014-11-03        kinaba: 				dist_leaf.emplace_back(calc_d(c, v), v);
143923277f 2014-11-03        kinaba: 			sort(dist_leaf.begin(), dist_leaf.end());
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 			for(int i=0; i<dist_leaf.size(); ++i)
143923277f 2014-11-03        kinaba: 			{
143923277f 2014-11-03        kinaba: 				const int cand_time = dist_leaf[i].first;
143923277f 2014-11-03        kinaba: 				if(i>0 && cand_time == dist_leaf[i-1].first)
143923277f 2014-11-03        kinaba: 					continue;
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 				// Light all leaves further or equal to dist_leaf[i].
143923277f 2014-11-03        kinaba: 				// Can the point |c| be the last point (burning at |cand_time|?)
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 				// Dijkstra.
143923277f 2014-11-03        kinaba: 				vector<int> burn_time(V, INF);
143923277f 2014-11-03        kinaba: 				{
143923277f 2014-11-03        kinaba: 					priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
143923277f 2014-11-03        kinaba: 					for(int k=i; k<dist_leaf.size(); ++k)
143923277f 2014-11-03        kinaba: 						Q.emplace(0, dist_leaf[k].second);
143923277f 2014-11-03        kinaba: 					while(!Q.empty()) {
143923277f 2014-11-03        kinaba: 						int d = Q.top().first;
143923277f 2014-11-03        kinaba: 						int v = Q.top().second;
143923277f 2014-11-03        kinaba: 						Q.pop();
143923277f 2014-11-03        kinaba: 						if(burn_time[v] != INF)
143923277f 2014-11-03        kinaba: 							continue;
143923277f 2014-11-03        kinaba: 						burn_time[v] = d;
143923277f 2014-11-03        kinaba: 						for(int i=0; i<G[v].size(); ++i)
143923277f 2014-11-03        kinaba: 						{
143923277f 2014-11-03        kinaba: 							int dd = G[v][i].first;
143923277f 2014-11-03        kinaba: 							int u = G[v][i].second;
143923277f 2014-11-03        kinaba: 							if(burn_time[u] == INF)
143923277f 2014-11-03        kinaba: 								Q.emplace(d+dd, u);
143923277f 2014-11-03        kinaba: 						}
143923277f 2014-11-03        kinaba: 					}
143923277f 2014-11-03        kinaba: 				}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 				int bt_min = INF;
143923277f 2014-11-03        kinaba: 				for(int e=0; e<E; ++e)
143923277f 2014-11-03        kinaba: 				{
143923277f 2014-11-03        kinaba: 					int a=A[e], b=B[e], ll=len[e], bt;
143923277f 2014-11-03        kinaba: 					if(burn_time[a]+ll == burn_time[b] || burn_time[b]+ll == burn_time[a]) {
143923277f 2014-11-03        kinaba: 						bt = max(burn_time[a], burn_time[b]);
143923277f 2014-11-03        kinaba: 					} else {
143923277f 2014-11-03        kinaba: 						bt = max(burn_time[a], burn_time[b]) + (ll -  abs(burn_time[b] - burn_time[a]))/2;
143923277f 2014-11-03        kinaba: 					}
143923277f 2014-11-03        kinaba: 					bt_min = min(bt_min, bt);
143923277f 2014-11-03        kinaba: 				}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 				if(bt_min >= cand_time)
143923277f 2014-11-03        kinaba: 					answer.insert(cand_time);
143923277f 2014-11-03        kinaba: 			}
143923277f 2014-11-03        kinaba: 		}
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: 		return answer.size();
143923277f 2014-11-03        kinaba: 	}
143923277f 2014-11-03        kinaba: };
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: // BEGIN CUT HERE
143923277f 2014-11-03        kinaba: #include <ctime>
143923277f 2014-11-03        kinaba: double start_time; string timer()
143923277f 2014-11-03        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
143923277f 2014-11-03        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
143923277f 2014-11-03        kinaba:  { os << "{ ";
143923277f 2014-11-03        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
143923277f 2014-11-03        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
143923277f 2014-11-03        kinaba: void verify_case(const int& Expected, const int& Received) {
143923277f 2014-11-03        kinaba:  bool ok = (Expected == Received);
143923277f 2014-11-03        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
143923277f 2014-11-03        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
143923277f 2014-11-03        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
143923277f 2014-11-03        kinaba: #define END	 verify_case(_, CandleTimer().differentTime(A, B, len));}
143923277f 2014-11-03        kinaba: int main(){
143923277f 2014-11-03        kinaba: 
143923277f 2014-11-03        kinaba: CASE(0)
143923277f 2014-11-03        kinaba: 	int A_[] = {0,1};
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = {1,2};
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = {10,1};
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = 2;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: CASE(1)
143923277f 2014-11-03        kinaba: 	int A_[] = {0,0,0};
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = {1,2,3};
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = {1,1,1};
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = 2;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: CASE(2)
143923277f 2014-11-03        kinaba: 	int A_[] = {0,0,0};
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = {1,2,3};
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = {1,2,3};
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = 4;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: CASE(3)
143923277f 2014-11-03        kinaba: 	int A_[] = {0,1,1,2,3,3,2,4};
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = {1,2,3,4,5,6,7,8};
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = {5,3,2,4,6,8,7,1};
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = 7;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: CASE(4)
143923277f 2014-11-03        kinaba: 	int A_[] = {0,0,0,0};
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = {1,2,3,4};
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = {123,456,789,1000};
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = 8;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: CASE(5)
143923277f 2014-11-03        kinaba: 	int A_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30};
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = {0,1,2,0,0,0,1,0,0,0,2,5,4,7,13,13,6,15,11,18,19,21,22,16,19,19,20,18,22,27};
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = {59,58,147,169,34,14,150,55,156,151,130,109,124,15,100,1,156,16,38,97,99,132,150,18,27,91,110,127,15,105};
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = 65;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: CASE(6)
143923277f 2014-11-03        kinaba: 	int A_[] = {0};
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = {1};
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = {1000};
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = 2;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: /*
143923277f 2014-11-03        kinaba: CASE(7)
143923277f 2014-11-03        kinaba: 	int A_[] = ;
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = ;
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = ;
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = ;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: CASE(8)
143923277f 2014-11-03        kinaba: 	int A_[] = ;
143923277f 2014-11-03        kinaba: 	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
143923277f 2014-11-03        kinaba: 	int B_[] = ;
143923277f 2014-11-03        kinaba: 	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
143923277f 2014-11-03        kinaba: 	int len_[] = ;
143923277f 2014-11-03        kinaba: 	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
143923277f 2014-11-03        kinaba: 	int _ = ;
143923277f 2014-11-03        kinaba: END
143923277f 2014-11-03        kinaba: */
143923277f 2014-11-03        kinaba: }
143923277f 2014-11-03        kinaba: // END CUT HERE