• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/603-U/1A.cpp version [825225f39a87e55b]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class MaxMinTreeGame { public:
           23  + int findend(vector <int> edges, vector <int> costs)
           24  + {
           25  +  int N = costs.size();
           26  +  vector<int> deg(N);
           27  +  for(int i=0; i<N-1; ++i) {
           28  +   deg[i+1]++;
           29  +   deg[edges[i]]++;
           30  +  }
           31  +  int maxLeaf = 0;
           32  +  for(int i=0; i<N; ++i)
           33  +   if(deg[i]==1)
           34  +    maxLeaf = max(maxLeaf, costs[i]);
           35  +  return maxLeaf;
           36  + }
           37  +};
           38  +
           39  +// BEGIN CUT HERE
           40  +#include <ctime>
           41  +double start_time; string timer()
           42  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           43  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           44  + { os << "{ ";
           45  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           46  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           47  +void verify_case(const int& Expected, const int& Received) {
           48  + bool ok = (Expected == Received);
           49  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           50  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           51  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           52  +#define END  verify_case(_, MaxMinTreeGame().findend(edges, costs));}
           53  +int main(){
           54  +
           55  +CASE(0)
           56  + int edges_[] = {0};
           57  +   vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_));
           58  + int costs_[] = {4,6};
           59  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
           60  + int _ = 6;
           61  +END
           62  +CASE(1)
           63  + int edges_[] = {0,1};
           64  +   vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_));
           65  + int costs_[] = {4,6,5};
           66  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
           67  + int _ = 5;
           68  +END
           69  +CASE(2)
           70  + int edges_[] = {0,1,2,3};
           71  +   vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_));
           72  + int costs_[] = {0,1,0,1,0};
           73  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
           74  + int _ = 0;
           75  +END
           76  +CASE(3)
           77  + int edges_[] = {0,0,0};
           78  +   vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_));
           79  + int costs_[] = {5,1,2,3};
           80  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
           81  + int _ = 3;
           82  +END
           83  +CASE(4)
           84  + int edges_[] = {0,0};
           85  +   vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_));
           86  + int costs_[] = {3,2,5};
           87  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
           88  + int _ = 5;
           89  +END
           90  +/*
           91  +CASE(6)
           92  + int edges_[] = ;
           93  +   vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_));
           94  + int costs_[] = ;
           95  +   vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
           96  + int _ = ;
           97  +END
           98  +*/
           99  +}
          100  +// END CUT HERE

Added SRM/603-U/2A.cpp version [9f6441ed525e874c]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +static const unsigned MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + unsigned val;
           26  + mint():val(0){}
           27  + mint(int      x):val(x%MODVAL) {}
           28  + mint(unsigned x):val(x%MODVAL) {}
           29  + mint(LL       x):val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint operator+(mint x, mint y) { return x+=y; }
           35  +mint operator-(mint x, mint y) { return x-=y; }
           36  +mint operator*(mint x, mint y) { return x*=y; }
           37  +
           38  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           39  +
           40  +class PairsOfStrings { public:
           41  + int getNumber(int n, int k)
           42  + {
           43  +  set<int> ds;
           44  +  for(int d=1; d*d<=n; ++d)
           45  +   if(n%d == 0) {
           46  +    ds.insert(d);
           47  +    ds.insert(n/d);
           48  +   }
           49  +
           50  +  memo.clear();
           51  +
           52  +  mint total = 0;
           53  +  for(int d: ds)
           54  +   total += count_unit(ds, d, k) * d;
           55  +  return total.val;
           56  + }
           57  +
           58  + map<int, mint> memo;
           59  + mint count_unit(const set<int>& ds, int d, int k)
           60  + {
           61  +  if(memo.count(d))
           62  +   return memo[d];
           63  +
           64  +  mint v = POW(k, d);
           65  +  for(int x: ds) {
           66  +   if(x>=d)
           67  +    break;
           68  +   if(d%x==0)
           69  +    v -= count_unit(ds, x, k);
           70  +  }
           71  +  return memo[d] = v;
           72  + }
           73  +};
           74  +
           75  +// BEGIN CUT HERE
           76  +#include <ctime>
           77  +double start_time; string timer()
           78  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           79  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           80  + { os << "{ ";
           81  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           82  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           83  +void verify_case(const int& Expected, const int& Received) {
           84  + bool ok = (Expected == Received);
           85  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           86  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           87  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           88  +#define END  verify_case(_, PairsOfStrings().getNumber(n, k));}
           89  +int main(){
           90  +
           91  +CASE(0)
           92  + int n = 2;
           93  + int k = 2;
           94  + int _ = 6;
           95  +END
           96  +CASE(1)
           97  + int n = 3;
           98  + int k = 2;
           99  + int _ = 20;
          100  +END
          101  +CASE(2)
          102  + int n = 3;
          103  + int k = 4;
          104  + int _ = 184;
          105  +END
          106  +CASE(3)
          107  + int n = 6;
          108  + int k = 2;
          109  + int _ = 348;
          110  +END
          111  +CASE(4)
          112  + int n = 100;
          113  + int k = 26;
          114  + int _ = 46519912;
          115  +END
          116  +CASE(5)
          117  + int n = 100000000;
          118  + int k = 26;
          119  + int _ = -1;
          120  +END
          121  +/*
          122  +CASE(6)
          123  + int n = ;
          124  + int k = ;
          125  + int _ = ;
          126  +END
          127  +*/
          128  +}
          129  +// END CUT HERE