b3c7c622f4 2015-12-18 kinaba: #include <iostream> b3c7c622f4 2015-12-18 kinaba: #include <sstream> b3c7c622f4 2015-12-18 kinaba: #include <iomanip> b3c7c622f4 2015-12-18 kinaba: #include <vector> b3c7c622f4 2015-12-18 kinaba: #include <string> b3c7c622f4 2015-12-18 kinaba: #include <map> b3c7c622f4 2015-12-18 kinaba: #include <set> b3c7c622f4 2015-12-18 kinaba: #include <algorithm> b3c7c622f4 2015-12-18 kinaba: #include <numeric> b3c7c622f4 2015-12-18 kinaba: #include <iterator> b3c7c622f4 2015-12-18 kinaba: #include <functional> b3c7c622f4 2015-12-18 kinaba: #include <complex> b3c7c622f4 2015-12-18 kinaba: #include <queue> b3c7c622f4 2015-12-18 kinaba: #include <stack> b3c7c622f4 2015-12-18 kinaba: #include <cmath> b3c7c622f4 2015-12-18 kinaba: #include <cassert> b3c7c622f4 2015-12-18 kinaba: #include <tuple> b3c7c622f4 2015-12-18 kinaba: using namespace std; b3c7c622f4 2015-12-18 kinaba: typedef long long LL; b3c7c622f4 2015-12-18 kinaba: typedef complex<double> CMP; b3c7c622f4 2015-12-18 kinaba: b3c7c622f4 2015-12-18 kinaba: class TreeAndPathLength3 { public: b3c7c622f4 2015-12-18 kinaba: vector <int> construct(int s) b3c7c622f4 2015-12-18 kinaba: { b3c7c622f4 2015-12-18 kinaba: if(s == 1) { b3c7c622f4 2015-12-18 kinaba: int ans[] = {0, 1, 1, 2, 2, 3}; b3c7c622f4 2015-12-18 kinaba: return vector<int>(ans+0, ans+6); b3c7c622f4 2015-12-18 kinaba: } b3c7c622f4 2015-12-18 kinaba: b3c7c622f4 2015-12-18 kinaba: // . - . - . - . -.-. b3c7c622f4 2015-12-18 kinaba: // n nodes -.-. b3c7c622f4 2015-12-18 kinaba: // -.-. b3c7c622f4 2015-12-18 kinaba: // -.-. k branches b3c7c622f4 2015-12-18 kinaba: // = b3c7c622f4 2015-12-18 kinaba: // (n-3) + k + k + k(k-1) b3c7c622f4 2015-12-18 kinaba: b3c7c622f4 2015-12-18 kinaba: int k=0; b3c7c622f4 2015-12-18 kinaba: for(; k+k+k*(k-1)<=s; ++k) {} b3c7c622f4 2015-12-18 kinaba: --k; b3c7c622f4 2015-12-18 kinaba: int n = s - k - k - k*(k-1) + 3; b3c7c622f4 2015-12-18 kinaba: b3c7c622f4 2015-12-18 kinaba: vector<int> edges; b3c7c622f4 2015-12-18 kinaba: for(int v=0; v<n-1; ++v) { b3c7c622f4 2015-12-18 kinaba: edges.emplace_back(v); b3c7c622f4 2015-12-18 kinaba: edges.emplace_back(v+1); b3c7c622f4 2015-12-18 kinaba: } b3c7c622f4 2015-12-18 kinaba: for(int u=0; u<k; ++u) { b3c7c622f4 2015-12-18 kinaba: edges.emplace_back(n-1); b3c7c622f4 2015-12-18 kinaba: edges.emplace_back(n+u); b3c7c622f4 2015-12-18 kinaba: edges.emplace_back(n+u); b3c7c622f4 2015-12-18 kinaba: edges.emplace_back(n+u+k); b3c7c622f4 2015-12-18 kinaba: } b3c7c622f4 2015-12-18 kinaba: return edges; b3c7c622f4 2015-12-18 kinaba: } b3c7c622f4 2015-12-18 kinaba: }; b3c7c622f4 2015-12-18 kinaba: b3c7c622f4 2015-12-18 kinaba: // BEGIN CUT HERE b3c7c622f4 2015-12-18 kinaba: #include <ctime> b3c7c622f4 2015-12-18 kinaba: double start_time; string timer() b3c7c622f4 2015-12-18 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } b3c7c622f4 2015-12-18 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) b3c7c622f4 2015-12-18 kinaba: { os << "{ "; b3c7c622f4 2015-12-18 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) b3c7c622f4 2015-12-18 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } b3c7c622f4 2015-12-18 kinaba: void verify_case(const vector <int>& Expected, const vector <int>& Received) { b3c7c622f4 2015-12-18 kinaba: bool ok = (Expected == Received); b3c7c622f4 2015-12-18 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; b3c7c622f4 2015-12-18 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } b3c7c622f4 2015-12-18 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); b3c7c622f4 2015-12-18 kinaba: #define END verify_case(_, TreeAndPathLength3().construct(s));} b3c7c622f4 2015-12-18 kinaba: int main(){ b3c7c622f4 2015-12-18 kinaba: b3c7c622f4 2015-12-18 kinaba: CASE(0) b3c7c622f4 2015-12-18 kinaba: int s = 1; b3c7c622f4 2015-12-18 kinaba: int __[] = {0, 1, 1, 2, 2, 3 }; b3c7c622f4 2015-12-18 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); b3c7c622f4 2015-12-18 kinaba: END b3c7c622f4 2015-12-18 kinaba: CASE(1) b3c7c622f4 2015-12-18 kinaba: int s = 2; b3c7c622f4 2015-12-18 kinaba: int __[] = {0, 1, 1, 2, 2, 3, 3, 4 }; b3c7c622f4 2015-12-18 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); b3c7c622f4 2015-12-18 kinaba: END b3c7c622f4 2015-12-18 kinaba: CASE(2) b3c7c622f4 2015-12-18 kinaba: int s = 6; b3c7c622f4 2015-12-18 kinaba: int __[] = {0, 1, 1, 2, 0, 3, 3, 4, 0, 5, 5, 6 }; b3c7c622f4 2015-12-18 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); b3c7c622f4 2015-12-18 kinaba: END b3c7c622f4 2015-12-18 kinaba: CASE(3) b3c7c622f4 2015-12-18 kinaba: int s = 8; b3c7c622f4 2015-12-18 kinaba: int __[] = {0, 1, 1, 2, 1, 3, 3, 4, 3, 5, 5, 6, 5, 7 }; b3c7c622f4 2015-12-18 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); b3c7c622f4 2015-12-18 kinaba: END b3c7c622f4 2015-12-18 kinaba: CASE(4) b3c7c622f4 2015-12-18 kinaba: int s = 10000; b3c7c622f4 2015-12-18 kinaba: int __[] = {1}; b3c7c622f4 2015-12-18 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); b3c7c622f4 2015-12-18 kinaba: END b3c7c622f4 2015-12-18 kinaba: /* b3c7c622f4 2015-12-18 kinaba: CASE(5) b3c7c622f4 2015-12-18 kinaba: int s = ; b3c7c622f4 2015-12-18 kinaba: int __[] = ; b3c7c622f4 2015-12-18 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); b3c7c622f4 2015-12-18 kinaba: END b3c7c622f4 2015-12-18 kinaba: */ b3c7c622f4 2015-12-18 kinaba: } b3c7c622f4 2015-12-18 kinaba: // END CUT HERE