Zombie March

zombie.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <map>
#include <cassert>
#include <vector>
using namespace std;

class Matrix {
  typedef std::map<size_t, std::map<size_t , double> > Mat_t;
  typedef typename Mat_t::iterator RowIter;
  typedef typename Mat_t::const_iterator RowCIter;
  typedef std::map<size_t, double> Col_t;
  typedef typename Col_t::iterator ColIter;
  typedef typename Col_t::const_iterator ColCIter;

  private:
    Mat_t mat;
    size_t n;

  public:
    Matrix(size_t n) : n(n) { }
    Matrix(size_t n, double v) : n(n) {
      for (int i = 0; i < n; ++ i) {
        set(i, i, v);
      }
    }

    inline size_t size() const {
      return n;
    }

    inline double get(size_t i, size_t j) const {
      assert(i <= n && j <= n);

      RowCIter rit = mat.find(i);
      if (rit == mat.end()) {
        return 0;
      }

      ColCIter cit = (rit->second).find(j);
      if (cit == (rit->second).end()) {
        return 0;
      }

      return cit->second;
    }

    inline void set(size_t i, size_t j, double v) {
      assert(i <= n && j <= n);

      mat[i][j] = v;
    }

    /**
     * y = A * x;
     * where A = this
     */
    std::vector<double> operator* (const std::vector<double>& x) const {
      assert(n == x.size());

      std::vector<double> y(n);
      for (RowCIter rit = mat.begin(); rit != mat.end(); ++ rit) {
        const Col_t& col = rit->second;
        double sum = 0;
        for (ColCIter cit = col.begin(); cit != col.end(); ++ cit) {
          sum += cit->second * x[cit->first];
        }
        y[rit->first] = sum;
      }

      return y;
    }

    /**
     * (*this) *= (x)
     */
    Matrix& operator *= (const Matrix& x) {
      Mat_t nMat;

      for (RowCIter rit = mat.begin(); rit != mat.end(); ++ rit) {
        const Col_t& col = rit->second;
        for (size_t i = 0; i < n; ++ i) {
          double sum = 0;
          for (ColCIter cit = col.begin(); cit != col.end(); ++ cit) {
            sum += cit->second * x.get(cit->first, i);
          }
          if (sum != 0) {
            nMat[rit->first][i] = sum;
          }
        }
      }
      mat.swap(nMat);
      return *this;
    }

    void toMarkovMatrix() {
      std::vector<size_t> count(n);
      for (RowIter rit = mat.begin(); rit != mat.end(); ++ rit) {
        Col_t& col = rit->second;
        for (ColIter cit = col.begin(); cit != col.end(); ++ cit) {
          count[cit->first] ++;
        }
      }

      for (RowIter rit = mat.begin(); rit != mat.end(); ++ rit) {
        Col_t& col = rit->second;
        for (ColIter cit = col.begin(); cit != col.end(); ++ cit) {
          cit->second /= count[cit->first];
        }
      }
    }

    void printMat() const {
      for (RowCIter rit = mat.begin(); rit != mat.end(); ++ rit) {
        const Col_t& col = rit->second;
        for (ColCIter cit = col.begin(); cit != col.end(); ++ cit) {
          std::cout << rit->first << ' ' << cit->first << ' ' << cit->second << endl;
        }
      }
    }
};

Matrix power(Matrix x, size_t n) {
  Matrix r(x.size(), 1);

  while (n) {
    if (n % 2) {
      r *= x;
    }
    x *= x;
    n /= 2;
  }

  return r;
}

int main(int argc , char * argv[]) {
  // cout.sync_with_stdio(false);
  // cin.sync_with_stdio(false);
  int t;
  // scanf("%d", &t);
  cin >> t;

  while (t --) {
    int N, M, k;
    // scanf("%d%d%d", &N, &M, &k);
    cin >> N >> M >> k;
    Matrix mat(N);
    vector<double> init(N);

    for (int i = 0; i < M; ++ i) {
      size_t u, v;
      // scanf("%ld%ld", &u, &v);
      cin >> u >> v;
      mat.set(u, v, 1);
      mat.set(v, u, 1);
    }

    mat.toMarkovMatrix();

    for (int i = 0; i < N; ++ i) {
      // scanf("%lf", &init[i]);
      cin >> init[i];
    }

    vector<double> result = power(mat, k) * init;

    sort(result.begin(), result.end(), greater<double>());

    for (int i = 0; i < 5; ++ i) {
      // printf("%d%c", (int) (result[i] + 0.5), (i == 4 ? '\n' : ' '));
      cout << ((int) (result[i] + 0.5));
      if (i == 4) {
        cout << endl;
      } else {
        cout << ' ';
      }
    }
  }
  return 0;
}

zombie_ac.cpp

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cmath>
using namespace std;

int main(int argc , char * argv[]) {
  int t;
  cin >> t;

  while (t --) {
    int N, M, k;
    cin >> N >> M >> k;
    vector<size_t> rows(N);
    vector<double> init(N);

    for (int i = 0; i < M; ++ i) {
      size_t u, v;
      cin >> u >> v;
      rows[u]++;
      rows[v]++;
    }

    for (int i = 0; i < N; ++ i) {
      // scanf("%lf", &init[i]);
      cin >> init[i];
    }

    vector<double> result;

    size_t total = 0;
    double nZombies = 0;
    for (int i = 0; i < N; ++ i) {
      if (rows[i] != 0) {
        total += rows[i];
        nZombies += init[i];
      }
    }

    result.resize(N);

    for (int i = 0; i < N; ++ i) {
      if (rows[i] != 0) {
        result[i] = rows[i] * nZombies / total;
      } else {
        result[i] = init[i];
      }
    }
    sort(result.begin(), result.end(), greater<double>());

    for (int i = 0; i < 5; ++ i) {
      // printf("%d%c", (int) (result[i] + 0.5), (i == 4 ? '\n' : ' '));
      cout << ((int) (result[i] + 0.5));
      if (i == 4) {
        cout << endl;
      } else {
        cout << ' ';
      }
      // cout << result[i] << ' ';
    }
    // cout << endl;
  }
  return 0;
}