ADDED   SRM/638-U/1A-U.cpp
Index: SRM/638-U/1A-U.cpp
==================================================================
--- SRM/638-U/1A-U.cpp
+++ SRM/638-U/1A-U.cpp
@@ -0,0 +1,199 @@
+#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;
+
+struct UnionFind
+{
+	vector<int> uf, sz;
+	int nc;
+
+	UnionFind(int N): uf(N), sz(N,1), nc(N)
+		{ for(int i=0; i<N; ++i) uf[i] = i; }
+	int size()
+		{ return nc; }
+	int size(int a)
+		{ return sz[Find(a)]; }
+	int Find(int a)
+		{ return uf[a]==a ? a : uf[a]=Find(uf[a]); }
+	bool Union(int a, int b)
+		{
+			a = Find(a);
+			b = Find(b);
+			if( a != b )
+			{
+				if( sz[a] >= sz[b] ) swap(a, b);
+				uf[a] = b;
+				sz[b] += sz[a];
+				--nc;
+			}
+			return (a!=b);
+		}
+};
+
+class ShadowSculpture { public:
+	string possible(vector <string> XY, vector <string> YZ, vector <string> ZX)
+	{
+		const int N = XY.size();
+
+		// Init
+		bool XYZ[10][10][10];
+		for(int x=0; x<N; ++x)
+		for(int y=0; y<N; ++y)
+		for(int z=0; z<N; ++z)
+			XYZ[x][y][z] = true;
+
+		// Grave
+		for(int x=0; x<N; ++x)
+		for(int y=0; y<N; ++y)
+		for(int z=0; z<N; ++z)
+			if(XY[x][y] == 'N' || YZ[y][z] == 'N' || ZX[z][x] == 'N')
+				XYZ[x][y][z] = false;
+
+		// Sanity check
+		for(int x=0; x<N; ++x)
+		for(int y=0; y<N; ++y) {
+			bool a=false,b=false,c=false;
+			for(int z=0; z<N; ++z) {
+				a |= XYZ[x][y][z];
+				b |= XYZ[z][x][y];
+				c |= XYZ[y][z][x];
+			}
+			if(XY[x][y]=='Y'&&!a) return "Impossible";
+			if(YZ[x][y]=='Y'&&!b) return "Impossible";
+			if(ZX[x][y]=='Y'&&!c) return "Impossible";
+		}
+
+		// Judge
+		return is_connected(XYZ, N) ? "Possible" : "Impossible";
+	}
+
+	bool is_connected(bool XYZ[10][10][10], int N)
+	{
+		UnionFind uf(N*N*N);
+		function<int(int,int,int)> id = [&](int x, int y, int z) {
+			return (x*N+y)*N+z;
+		};
+
+		const int dx[] = {-1,+1,0,0,0,0};
+		const int dy[] = {0,0,-1,+1,0,0};
+		const int dz[] = {0,0,0,0,-1,+1};
+		int cnt = 0;
+		for(int x=0; x<N; ++x)
+		for(int y=0; y<N; ++y)
+		for(int z=0; z<N; ++z) if(XYZ[x][y][z]) {
+			++cnt;
+			for(int d=0; d<6; ++d) {
+				int xx=x+dx[d], yy=y+dy[d], zz=z+dz[d];
+				if(0<=xx&&xx<N&&0<=yy&&yy<N&&0<=zz&&zz<N&&XYZ[xx][yy][zz])
+					uf.Union(id(x,y,z), id(xx,yy,zz));
+			}
+		}
+
+		for(int x=0; x<N; ++x)
+		for(int y=0; y<N; ++y)
+		for(int z=0; z<N; ++z) if(XYZ[x][y][z] && uf.size(id(x,y,z))!=cnt)
+			return false;
+		return true;
+	}
+};
+
+// 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 string& Expected, const string& 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(_, ShadowSculpture().possible(XY, YZ, ZX));}
+int main(){
+
+CASE(0)
+	string XY_[] = {"YN","NN"};
+	  vector <string> XY(XY_, XY_+sizeof(XY_)/sizeof(*XY_)); 
+	string YZ_[] = {"YN","NN"};
+	  vector <string> YZ(YZ_, YZ_+sizeof(YZ_)/sizeof(*YZ_)); 
+	string ZX_[] = {"YN","NN"};
+	  vector <string> ZX(ZX_, ZX_+sizeof(ZX_)/sizeof(*ZX_)); 
+	string _ = "Possible"; 
+END
+CASE(1)
+	string XY_[] = {"YN","NY"};
+	  vector <string> XY(XY_, XY_+sizeof(XY_)/sizeof(*XY_)); 
+	string YZ_[] = {"YN","NY"};
+	  vector <string> YZ(YZ_, YZ_+sizeof(YZ_)/sizeof(*YZ_)); 
+	string ZX_[] = {"YN","NY"};
+	  vector <string> ZX(ZX_, ZX_+sizeof(ZX_)/sizeof(*ZX_)); 
+	string _ = "Impossible"; 
+END
+CASE(2)
+	string XY_[] = {"YYY","YNY","YYY"};
+	  vector <string> XY(XY_, XY_+sizeof(XY_)/sizeof(*XY_)); 
+	string YZ_[] = {"YYY","YNY","YYY"};
+	  vector <string> YZ(YZ_, YZ_+sizeof(YZ_)/sizeof(*YZ_)); 
+	string ZX_[] = {"YYY","YNY","YYY"};
+	  vector <string> ZX(ZX_, ZX_+sizeof(ZX_)/sizeof(*ZX_)); 
+	string _ = "Possible"; 
+END
+CASE(3)
+	string XY_[] = {"YYY","YNY","YYY"};
+	  vector <string> XY(XY_, XY_+sizeof(XY_)/sizeof(*XY_)); 
+	string YZ_[] = {"NYY","YNY","YYY"};
+	  vector <string> YZ(YZ_, YZ_+sizeof(YZ_)/sizeof(*YZ_)); 
+	string ZX_[] = {"YYY","YNY","YYN"};
+	  vector <string> ZX(ZX_, ZX_+sizeof(ZX_)/sizeof(*ZX_)); 
+	string _ = "Impossible"; 
+END
+CASE(4)
+	string XY_[] = {"N"};
+	  vector <string> XY(XY_, XY_+sizeof(XY_)/sizeof(*XY_)); 
+	string YZ_[] = {"N"};
+	  vector <string> YZ(YZ_, YZ_+sizeof(YZ_)/sizeof(*YZ_)); 
+	string ZX_[] = {"N"};
+	  vector <string> ZX(ZX_, ZX_+sizeof(ZX_)/sizeof(*ZX_)); 
+	string _ = "Possible"; 
+END
+/*
+CASE(5)
+	string XY_[] = ;
+	  vector <string> XY(XY_, XY_+sizeof(XY_)/sizeof(*XY_)); 
+	string YZ_[] = ;
+	  vector <string> YZ(YZ_, YZ_+sizeof(YZ_)/sizeof(*YZ_)); 
+	string ZX_[] = ;
+	  vector <string> ZX(ZX_, ZX_+sizeof(ZX_)/sizeof(*ZX_)); 
+	string _ = ; 
+END
+CASE(6)
+	string XY_[] = ;
+	  vector <string> XY(XY_, XY_+sizeof(XY_)/sizeof(*XY_)); 
+	string YZ_[] = ;
+	  vector <string> YZ(YZ_, YZ_+sizeof(YZ_)/sizeof(*YZ_)); 
+	string ZX_[] = ;
+	  vector <string> ZX(ZX_, ZX_+sizeof(ZX_)/sizeof(*ZX_)); 
+	string _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/638-U/1B.cpp
Index: SRM/638-U/1B.cpp
==================================================================
--- SRM/638-U/1B.cpp
+++ SRM/638-U/1B.cpp
@@ -0,0 +1,111 @@
+#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 MODVAL = 1000000007;
+
+class NarrowPassage2 { public:
+	int count(vector <int> size, int maxSizeSum)
+	{
+		if(size.size() <= 1)
+			return 1;
+
+		int mi = min_element(size.begin(), size.end()) - size.begin();
+
+		int lm=mi;
+		for(int k=mi-1; k>=0 && size[k]+size[mi]<=maxSizeSum; --k)
+			lm = k;
+		int rm=mi;
+		for(int k=mi+1; k<size.size() && size[k]+size[mi]<=maxSizeSum; ++k)
+			rm = k;
+
+		size.erase(size.begin()+mi);
+		return LL(rm-lm+1) * count(size, maxSizeSum) % MODVAL;
+	}
+};
+
+// 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(_, NarrowPassage2().count(size, maxSizeSum));}
+int main(){
+
+CASE(0)
+	int size_[] = {1, 2, 3};
+	  vector <int> size(size_, size_+sizeof(size_)/sizeof(*size_)); 
+	int maxSizeSum = 3; 
+	int _ = 2; 
+END
+CASE(1)
+	int size_[] = {1, 2, 3};
+	  vector <int> size(size_, size_+sizeof(size_)/sizeof(*size_)); 
+	int maxSizeSum = 1000; 
+	int _ = 6; 
+END
+CASE(2)
+	int size_[] = {1, 2, 3};
+	  vector <int> size(size_, size_+sizeof(size_)/sizeof(*size_)); 
+	int maxSizeSum = 4; 
+	int _ = 3; 
+END
+CASE(3)
+	int size_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1};
+	  vector <int> size(size_, size_+sizeof(size_)/sizeof(*size_)); 
+	int maxSizeSum = 2; 
+	int _ = 227020758; 
+END
+CASE(4)
+	int size_[] = {2,4,6,1,3,5};
+	  vector <int> size(size_, size_+sizeof(size_)/sizeof(*size_)); 
+	int maxSizeSum = 8; 
+	int _ = 60; 
+END
+CASE(5)
+	int size_[] = {1000000000};
+	  vector <int> size(size_, size_+sizeof(size_)/sizeof(*size_)); 
+	int maxSizeSum = 1000000000; 
+	int _ = 1; 
+END
+/*
+CASE(6)
+	int size_[] = ;
+	  vector <int> size(size_, size_+sizeof(size_)/sizeof(*size_)); 
+	int maxSizeSum = ; 
+	int _ = ; 
+END
+CASE(7)
+	int size_[] = ;
+	  vector <int> size(size_, size_+sizeof(size_)/sizeof(*size_)); 
+	int maxSizeSum = ; 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/638-U/1C-U.cpp
Index: SRM/638-U/1C-U.cpp
==================================================================
--- SRM/638-U/1C-U.cpp
+++ SRM/638-U/1C-U.cpp
@@ -0,0 +1,278 @@
+#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