Artifact Content
Not logged in

Artifact a8492d73123f6c2f7ae0e4d74d822780335e83dc


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

const int INF = 0x1fffffff;

class CandleTimer { public:
	int differentTime(vector <int> A, vector <int> B, vector <int> len)
	{
		if(A.size() == 1) {
			// Special case, just in case. All nodes are leaves.
			// Either light only one end or both ends.
			return 2;
		}

		// x2, to make all the possible final points on integer coordinates.
		for(auto& li: len)
			li *= 2;

		// Prepare....
		const int E = A.size(), V = E+1;

		vector<int> leaf;
		vector<bool> is_leaf(V, false);
		{
			vector<int> degree(V);
			for(auto a: A) degree[a]++;
			for(auto b: B) degree[b]++;

			for(int v=0; v<V; ++v)
				if(degree[v]==1) {
					leaf.push_back(v);
					is_leaf[v] = true;
				}
		}

		vector<vector<int>> dist(V, vector<int>(V, INF));
		{
			for(int i=0; i<V; ++i)
				dist[i][i] = 0;
			for(int i=0; i<E; ++i)
				dist[A[i]][B[i]] = dist[B[i]][A[i]] = len[i];
			for(int k=0; k<V; ++k)
			for(int i=0; i<V; ++i)
			for(int j=0; j<V; ++j)
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
		}

		vector<vector<pair<int,int>>> G(V); // len, dest
		for(int e=0; e<E; ++e) {
			G[A[e]].emplace_back(len[e], B[e]);
			G[B[e]].emplace_back(len[e], A[e]);
		}

		// Compute all possible final points.
		enum {EID, POS};
		vector<tuple<int,int>> cand;
		{
			vector<bool> done(V, false);

			// Add all leaves as the possible final point
			for(int e=0; e<E; ++e) {
				if(is_leaf[A[e]] && !done[A[e]])
					cand.emplace_back(e, 0), done[A[e]]=true;
				if(is_leaf[B[e]] && !done[B[e]])
					cand.emplace_back(e, len[e]), done[B[e]]=true;
			}

			// Add all mid points.
			for(int la: leaf)
			for(int lb: leaf)
			for(int e=0; e<E; ++e)
			{
				int a=A[e], b=B[e], ll=len[e];
				if(dist[la][a]+ll+dist[lb][b] == dist[la][lb]) {
					if(abs(dist[la][a] - dist[lb][b]) <= ll) {
						tuple<int,int> c(e, (ll+dist[lb][b]-dist[la][a])/2);
						// TODO: reduce by done[]
						cand.push_back(c);
					}
				} else if(dist[la][b]+ll+dist[lb][a] == dist[la][lb]) {
					if(abs(dist[la][b] - dist[lb][a]) <= ll) {
						tuple<int,int> c(e, (ll+dist[la][b]-dist[lb][a])/2);
						// TODO: reduce by done[]
						cand.push_back(c);
					}
				}
			}
		}

		// Distance between a candidate point and a node.
		function<int(tuple<int,int>,int)> calc_d = [&](tuple<int,int> c, int v) {
			return min(
				dist[A[get<EID>(c)]][v] + get<POS>(c),
				dist[B[get<EID>(c)]][v] + len[get<EID>(c)] - get<POS>(c)
			);
		};

		// Simulate all.
		set<int> answer;
		for(auto c: cand)
		{
			vector<pair<int,int>> dist_leaf;
			for(int v: leaf)
				dist_leaf.emplace_back(calc_d(c, v), v);
			sort(dist_leaf.begin(), dist_leaf.end());

			for(int i=0; i<dist_leaf.size(); ++i)
			{
				const int cand_time = dist_leaf[i].first;
				if(i>0 && cand_time == dist_leaf[i-1].first)
					continue;

				// Light all leaves further or equal to dist_leaf[i].
				// Can the point |c| be the last point (burning at |cand_time|?)

				// Dijkstra.
				vector<int> burn_time(V, INF);
				{
					priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
					for(int k=i; k<dist_leaf.size(); ++k)
						Q.emplace(0, dist_leaf[k].second);
					while(!Q.empty()) {
						int d = Q.top().first;
						int v = Q.top().second;
						Q.pop();
						if(burn_time[v] != INF)
							continue;
						burn_time[v] = d;
						for(int i=0; i<G[v].size(); ++i)
						{
							int dd = G[v][i].first;
							int u = G[v][i].second;
							if(burn_time[u] == INF)
								Q.emplace(d+dd, u);
						}
					}
				}

				int bt_min = INF;
				for(int e=0; e<E; ++e)
				{
					int a=A[e], b=B[e], ll=len[e], bt;
					if(burn_time[a]+ll == burn_time[b] || burn_time[b]+ll == burn_time[a]) {
						bt = max(burn_time[a], burn_time[b]);
					} else {
						bt = max(burn_time[a], burn_time[b]) + (ll -  abs(burn_time[b] - burn_time[a]))/2;
					}
					bt_min = min(bt_min, bt);
				}

				if(bt_min >= cand_time)
					answer.insert(cand_time);
			}
		}

		return answer.size();
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, CandleTimer().differentTime(A, B, len));}
int main(){

CASE(0)
	int A_[] = {0,1};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {1,2};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int len_[] = {10,1};
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = 2; 
END
CASE(1)
	int A_[] = {0,0,0};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {1,2,3};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int len_[] = {1,1,1};
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = 2; 
END
CASE(2)
	int A_[] = {0,0,0};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {1,2,3};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int len_[] = {1,2,3};
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = 4; 
END
CASE(3)
	int A_[] = {0,1,1,2,3,3,2,4};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {1,2,3,4,5,6,7,8};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int len_[] = {5,3,2,4,6,8,7,1};
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = 7; 
END
CASE(4)
	int A_[] = {0,0,0,0};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {1,2,3,4};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int len_[] = {123,456,789,1000};
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = 8; 
END
CASE(5)
	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};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	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};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	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};
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = 65; 
END
CASE(6)
	int A_[] = {0};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {1};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int len_[] = {1000};
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = 2; 
END
/*
CASE(7)
	int A_[] = ;
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = ;
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int len_[] = ;
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = ; 
END
CASE(8)
	int A_[] = ;
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = ;
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int len_[] = ;
	  vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 
	int _ = ; 
END
*/
}
// END CUT HERE