589fb61dc1 2014-08-30 kinaba: #include <iostream> 589fb61dc1 2014-08-30 kinaba: #include <sstream> 589fb61dc1 2014-08-30 kinaba: #include <iomanip> 589fb61dc1 2014-08-30 kinaba: #include <vector> 589fb61dc1 2014-08-30 kinaba: #include <string> 589fb61dc1 2014-08-30 kinaba: #include <map> 589fb61dc1 2014-08-30 kinaba: #include <set> 589fb61dc1 2014-08-30 kinaba: #include <algorithm> 589fb61dc1 2014-08-30 kinaba: #include <numeric> 589fb61dc1 2014-08-30 kinaba: #include <iterator> 589fb61dc1 2014-08-30 kinaba: #include <functional> 589fb61dc1 2014-08-30 kinaba: #include <complex> 589fb61dc1 2014-08-30 kinaba: #include <queue> 589fb61dc1 2014-08-30 kinaba: #include <stack> 589fb61dc1 2014-08-30 kinaba: #include <cmath> 589fb61dc1 2014-08-30 kinaba: #include <cassert> 589fb61dc1 2014-08-30 kinaba: #include <tuple> 589fb61dc1 2014-08-30 kinaba: using namespace std; 589fb61dc1 2014-08-30 kinaba: typedef long long LL; 589fb61dc1 2014-08-30 kinaba: typedef complex<double> CMP; 589fb61dc1 2014-08-30 kinaba: 589fb61dc1 2014-08-30 kinaba: class Egalitarianism3 { public: 589fb61dc1 2014-08-30 kinaba: int maxCities(int n, vector <int> a, vector <int> b, vector <int> len) 589fb61dc1 2014-08-30 kinaba: { 589fb61dc1 2014-08-30 kinaba: if(n<=2) 589fb61dc1 2014-08-30 kinaba: return n; 589fb61dc1 2014-08-30 kinaba: 589fb61dc1 2014-08-30 kinaba: const int INF = 0x3fffffff; 589fb61dc1 2014-08-30 kinaba: vector<vector<int>> d(n, vector<int>(n, INF)); 589fb61dc1 2014-08-30 kinaba: for(int i=0; i<n; ++i) 589fb61dc1 2014-08-30 kinaba: d[i][i] = 0; 589fb61dc1 2014-08-30 kinaba: for(int i=0; i<a.size(); ++i) { 589fb61dc1 2014-08-30 kinaba: d[a[i]-1][b[i]-1] = len[i]; 589fb61dc1 2014-08-30 kinaba: d[b[i]-1][a[i]-1] = len[i]; 589fb61dc1 2014-08-30 kinaba: } 589fb61dc1 2014-08-30 kinaba: for(int k=0; k<n; ++k) 589fb61dc1 2014-08-30 kinaba: for(int i=0; i<n; ++i) 589fb61dc1 2014-08-30 kinaba: for(int j=0; j<n; ++j) 589fb61dc1 2014-08-30 kinaba: d[i][j] = min(d[i][j], d[i][k]+d[k][j]); 589fb61dc1 2014-08-30 kinaba: 589fb61dc1 2014-08-30 kinaba: int best = 2; 589fb61dc1 2014-08-30 kinaba: for(int c=0; c<n; ++c) { 589fb61dc1 2014-08-30 kinaba: map<int, vector<int>> cand; 589fb61dc1 2014-08-30 kinaba: for(int v=0; v<n; ++v) if(v!=c) { 589fb61dc1 2014-08-30 kinaba: int rad = d[c][v]; 589fb61dc1 2014-08-30 kinaba: bool ok = true; 589fb61dc1 2014-08-30 kinaba: for(int u: cand[rad]) 589fb61dc1 2014-08-30 kinaba: if(d[v][u] != 2*rad) 589fb61dc1 2014-08-30 kinaba: ok = false; 589fb61dc1 2014-08-30 kinaba: if(ok) { 589fb61dc1 2014-08-30 kinaba: cand[rad].push_back(v); 589fb61dc1 2014-08-30 kinaba: best = max<int>(best, cand[rad].size()); 589fb61dc1 2014-08-30 kinaba: } 589fb61dc1 2014-08-30 kinaba: } 589fb61dc1 2014-08-30 kinaba: } 589fb61dc1 2014-08-30 kinaba: return best; 589fb61dc1 2014-08-30 kinaba: } 589fb61dc1 2014-08-30 kinaba: }; 589fb61dc1 2014-08-30 kinaba: 589fb61dc1 2014-08-30 kinaba: // BEGIN CUT HERE 589fb61dc1 2014-08-30 kinaba: #include <ctime> 589fb61dc1 2014-08-30 kinaba: double start_time; string timer() 589fb61dc1 2014-08-30 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 589fb61dc1 2014-08-30 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 589fb61dc1 2014-08-30 kinaba: { os << "{ "; 589fb61dc1 2014-08-30 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 589fb61dc1 2014-08-30 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 589fb61dc1 2014-08-30 kinaba: void verify_case(const int& Expected, const int& Received) { 589fb61dc1 2014-08-30 kinaba: bool ok = (Expected == Received); 589fb61dc1 2014-08-30 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 589fb61dc1 2014-08-30 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 589fb61dc1 2014-08-30 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 589fb61dc1 2014-08-30 kinaba: #define END verify_case(_, Egalitarianism3().maxCities(n, a, b, len));} 589fb61dc1 2014-08-30 kinaba: int main(){ 589fb61dc1 2014-08-30 kinaba: 589fb61dc1 2014-08-30 kinaba: CASE(0) 589fb61dc1 2014-08-30 kinaba: int n = 4; 589fb61dc1 2014-08-30 kinaba: int a_[] = {1,1,1}; 589fb61dc1 2014-08-30 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 589fb61dc1 2014-08-30 kinaba: int b_[] = {2,3,4}; 589fb61dc1 2014-08-30 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 589fb61dc1 2014-08-30 kinaba: int len_[] = {1,1,1}; 589fb61dc1 2014-08-30 kinaba: vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 589fb61dc1 2014-08-30 kinaba: int _ = 3; 589fb61dc1 2014-08-30 kinaba: END 589fb61dc1 2014-08-30 kinaba: CASE(1) 589fb61dc1 2014-08-30 kinaba: int n = 6; 589fb61dc1 2014-08-30 kinaba: int a_[] = {1,2,3,2,3}; 589fb61dc1 2014-08-30 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 589fb61dc1 2014-08-30 kinaba: int b_[] = {2,3,4,5,6}; 589fb61dc1 2014-08-30 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 589fb61dc1 2014-08-30 kinaba: int len_[] = {2,1,3,2,3}; 589fb61dc1 2014-08-30 kinaba: vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 589fb61dc1 2014-08-30 kinaba: int _ = 3; 589fb61dc1 2014-08-30 kinaba: END 589fb61dc1 2014-08-30 kinaba: CASE(2) 589fb61dc1 2014-08-30 kinaba: int n = 10; 589fb61dc1 2014-08-30 kinaba: int a_[] = {1,1,1,1,1,1,1,1,1}; 589fb61dc1 2014-08-30 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 589fb61dc1 2014-08-30 kinaba: int b_[] = {2,3,4,5,6,7,8,9,10}; 589fb61dc1 2014-08-30 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 589fb61dc1 2014-08-30 kinaba: int len_[] = {1000,1000,1000,1000,1000,1000,1000,1000,1000}; 589fb61dc1 2014-08-30 kinaba: vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 589fb61dc1 2014-08-30 kinaba: int _ = 9; 589fb61dc1 2014-08-30 kinaba: END 589fb61dc1 2014-08-30 kinaba: CASE(3) 589fb61dc1 2014-08-30 kinaba: int n = 1; 589fb61dc1 2014-08-30 kinaba: vector <int> a; 589fb61dc1 2014-08-30 kinaba: vector <int> b; 589fb61dc1 2014-08-30 kinaba: vector <int> len; 589fb61dc1 2014-08-30 kinaba: int _ = 1; 589fb61dc1 2014-08-30 kinaba: END 589fb61dc1 2014-08-30 kinaba: /* 589fb61dc1 2014-08-30 kinaba: CASE(4) 589fb61dc1 2014-08-30 kinaba: int n = ; 589fb61dc1 2014-08-30 kinaba: int a_[] = ; 589fb61dc1 2014-08-30 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 589fb61dc1 2014-08-30 kinaba: int b_[] = ; 589fb61dc1 2014-08-30 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 589fb61dc1 2014-08-30 kinaba: int len_[] = ; 589fb61dc1 2014-08-30 kinaba: vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 589fb61dc1 2014-08-30 kinaba: int _ = ; 589fb61dc1 2014-08-30 kinaba: END 589fb61dc1 2014-08-30 kinaba: CASE(5) 589fb61dc1 2014-08-30 kinaba: int n = ; 589fb61dc1 2014-08-30 kinaba: int a_[] = ; 589fb61dc1 2014-08-30 kinaba: vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); 589fb61dc1 2014-08-30 kinaba: int b_[] = ; 589fb61dc1 2014-08-30 kinaba: vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); 589fb61dc1 2014-08-30 kinaba: int len_[] = ; 589fb61dc1 2014-08-30 kinaba: vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_)); 589fb61dc1 2014-08-30 kinaba: int _ = ; 589fb61dc1 2014-08-30 kinaba: END 589fb61dc1 2014-08-30 kinaba: */ 589fb61dc1 2014-08-30 kinaba: } 589fb61dc1 2014-08-30 kinaba: // END CUT HERE