UVa 11733 - Airports

Accepted date: 2014-06-17
Ranking (as of 2014-06-18): 69 out of 874
Language: C++

/*
  UVa 11733 - Airports

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11733_Airports.cpp
*/

#include <algorithm>
#include <cstdio>
using namespace std;

const int n_max = 10000, m_max = 100000;
class union_find {
public:
  void init(int n);
  int find(int i) const;
  int do_union(int i, int j);
    // generate the union of the two sets to which i and j belong and 
    // return the representative of the result set
  int nr_sets() const {return s_;}

private:
  int n_; // number of elements
  int s_; // number of sets
  int representatives_[n_max];
    // representatives[i] is the representative of a set to which i belongs
  int ranks_[n_max];
    // ranks_[i] is the number of elements in the set to which i belongs
} vertices;

void union_find::init(int n)
{
  n_ = s_ = n;
  for (int i = 0; i < n_; i++) {
    representatives_[i] = i;
    ranks_[i] = 1;
  }
}

int union_find::find(int i) const
// return the representative of a set to which i belongs
{
  return (representatives_[i] == i) ? i : find(representatives_[i]);
}

int union_find::do_union(int i, int j)
// generate the union of the two sets to which i and j belong and 
// return the representative of the result set
{
  int ri = find(i), rj = find(j);
  if (ri == rj) // already in the same set
    return -1;
  s_--;
  if (ranks_[ri] >= ranks_[rj]) {
    ranks_[ri] += ranks_[rj];
    representatives_[rj] = ri;
    return ri;
  }
  else {
    ranks_[rj] += ranks_[ri];
    representatives_[ri] = rj;
    return rj;
  }
}

struct edge {
  int u_, v_, weight_;
  bool operator<(const edge& e) const {return weight_ < e.weight_;}
} edges[m_max];

int main()
{
  int t;
  scanf("%d", &t);
  for (int tc = 1; tc <= t; tc++) {
    int n, m, a;
    scanf("%d %d %d", &n, &m, &a);
    for (int i = 0; i < m; i++) {
      int x, y, c;
      scanf("%d %d %d", &edges[i].u_, &edges[i].v_, &edges[i].weight_);
      edges[i].u_--; edges[i].v_--;
    }
    // apply Kruskal's minimum spanning tree algorithm
    vertices.init(n);
    sort(edges, edges + m); // sort the edges in ascending order of their weights
    int cost = 0;
    for (int i = 0; i < m && edges[i].weight_ < a; i++)
      if (vertices.find(edges[i].u_) != vertices.find(edges[i].v_)) {
        vertices.do_union(edges[i].u_, edges[i].v_);
        cost += edges[i].weight_;
        if (vertices.nr_sets() == 1)
          break;
      }
    printf("Case #%d: %d %d\n",
      tc, cost + a * vertices.nr_sets(), vertices.nr_sets());
  }
  return 0;
}

UVa 10525 - New to Bangladesh?

Accepted date: 2014-06-16
Ranking (as of 2014-06-16): 211 out of 302
Language: C++

/*
  UVa 10525 - New to Bangladesh?

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10525_New_to_Bangladesh.cpp
*/

#include <iostream>
#include <vector>
#include <utility>
#include <limits>
using namespace std;

struct edge {
  int u_; // source vertex
  int v_; // destination vertex
  int t_; // time
  int l_; // length

  edge() : u_(-1), v_(-1), t_(-1), l_(-1) {}
  edge(int u, int v, int t, int l) : u_(u), v_(v), t_(t), l_(l) {}
};

pair<int, int> bellman_ford(int n, int s, int t, const vector<edge>& edges)
{
  // apply the Bellman-Ford's shortest path algorithm
  // initialize the graph
  vector< pair<int, int> > distances(n,
    make_pair(numeric_limits<int>::max(), numeric_limits<int>::max()));
  distances[s].first = distances[s].second = 0;
  // relax the edges repeatedly
  for (int i = 0; i < n - 1; i++)
    for (size_t j = 0, je = edges.size(); j < je; j++) {
      const edge& e = edges[j];
      long long lt = static_cast<long long>(distances[e.u_].first),
        ll = static_cast<long long>(distances[e.u_].second);
      if (lt + e.t_ < distances[e.v_].first ||
        lt + e.t_ == distances[e.v_].first && ll + e.l_ < distances[e.v_].second)
        distances[e.v_] =
          make_pair(distances[e.u_].first + e.t_, distances[e.u_].second + e.l_);
    }
  return distances[t];
}

int main()
{
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<edge> edges(m * 2);
    for (int i = 0; i < m; i++) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      a--; b--;
      edges[i * 2].u_ = edges[i * 2 + 1].v_ = a;
      edges[i * 2].v_ = edges[i * 2 + 1].u_ = b;
      edges[i * 2].t_ = edges[i * 2 + 1].t_ = c;
      edges[i * 2].l_ = edges[i * 2 + 1].l_ = d;
    }
    int q;
    cin >> q;
    while (q--) {
      int s, t;
      cin >> s >> t;
      pair<int, int> d = bellman_ford(n, s - 1, t - 1, edges);
      if (d.first != numeric_limits<int>::max())
        cout << "Distance and time to reach destination is " << d.second <<
          " & " << d.first << ".\n";
      else
        cout << "No Path.\n";
    }
    if (t)
      cout << endl;
  }
  return 0;
}

UVa 10947 - Bear with me, again..

Accepted date: 2014-06-15
Ranking (as of 2014-06-15): 238 out of 517
Language: C++

/*
  UVa 10947 - Bear with me, again..

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10947_Bear_with_me_again.cpp
*/

#include <cstdio>
#include <cmath>

const int n_max = 100;

struct island {
  int x_, y_, r_;
} islands[n_max + 2];

bool matrix[n_max + 2][n_max + 2];

void floyd_warshall(int n)
{
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (matrix[i][k] && matrix[k][j])
          matrix[i][j] = true;
}

int main()
{
  int k, m;
  while (scanf("%d %d", &k, &m) != EOF) {
    double d_max = static_cast<double>(k) * m;
    scanf("%d %d %d", &islands[0].x_, &islands[0].y_, &islands[0].r_);
      // current island
    scanf("%d %d %d", &islands[1].x_, &islands[1].y_, &islands[1].r_);
      // home island
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%d %d %d",
        &islands[i + 2].x_, &islands[i + 2].y_, &islands[i + 2].r_);
    for (int i = 0; i < n + 2; i++) {
      matrix[i][i] = true;
      for (int j = i + 1; j < n + 2; j++) {
        double dx = islands[i].x_ - islands[j].x_,
          dy = islands[i].y_ - islands[j].y_;
        double d = dx * dx + dy * dy,
          dr = d_max + islands[i].r_ + islands[j].r_;
        matrix[i][j] = matrix[j][i] = d <= dr * dr;
          // sqrt(d) - islands[i].r_ - islands[j].r_ <= dr
      }
    }
    floyd_warshall(n + 2);
    puts((matrix[0][1]) ? "Larry and Ryan will escape!" :
      "Larry and Ryan will be eaten to death.");
  }
  return 0;
}

UVa 10356 - Rough Roads

Accepted date: 2014-06-12
Ranking (as of 2014-06-12): 151 out of 612
Language: C++

/*
  UVa 10356 - Rough Roads

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10356_Rough_Roads.cpp
*/

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <limits>
using namespace std;

const int n_max = 500;

struct edge {
  int v_;
  int w_;
  edge(int v, int w) : v_(v), w_(w) {}
};

vector<edge> edges[n_max];
int distances[n_max][2];
  // distances[i][0] is the distance of i-th junction riding the cycyle
  // distances[i][1] is the distance of i-th junction carrying the cycle
bool visited[n_max][2];
  // visited[i][0] is true if i-th junction has already 
  // been reached riding the cycle
  // visited[i][1] is true if i-th junction has already 
  // been reached carrying the cycle

struct distance_comparator {
  bool operator () (const pair<int, int>& i, const pair<int, int>& j) const
  {
    if(distances[i.first][i.second] == distances[j.first][j.second])
      return i < j;
    else
      return distances[i.first][i.second] < distances[j.first][j.second];
  }
};

int dijkstra_shortest_path(int n)
{
  for (int i = 0 ; i < n; i++) {
    distances[i][0] = distances[i][1] = numeric_limits<int>::max();
    visited[i][0] = visited[i][1] = false;
  }
  distances[0][0] = 0;
  set <pair<int, int>, distance_comparator> pq; // priority queue
  pq.insert(make_pair(0, 0));
  while(!pq.empty()) {
    pair<int, int> u = *pq.begin();
    pq.erase(pq.begin());
    visited[u.first][u.second] = true;
    if (u.first == n - 1 && u.second == 0)
      break;
    int d = distances[u.first][u.second], second = 1 - u.second;
    const vector<edge>& e = edges[u.first];
    for (size_t i = 0; i < e.size(); i++)
      if (!visited[e[i].v_][second] &&
        distances[e[i].v_][second] > d + e[i].w_) {
        pair<int, int> v = make_pair(e[i].v_, second);
        pq.erase(v); // remove v if it has already been in the queue
        distances[e[i].v_][second] = d + e[i].w_;
        pq.insert(v);
      }
  }
  return distances[n - 1][0];
}

int main()
{
  int n, r;
  for (int s = 1; cin >> n >> r; s++) {
    for (int i = 0; i < n; i++)
      edges[i].clear();
    while (r--) {
      int u, v, l;
      cin >> u >> v >> l;
      edges[u].push_back(edge(v, l));
      edges[v].push_back(edge(u, l));
    }
    int d = dijkstra_shortest_path(n);
    cout << "Set #" << s << endl;
    if (d != numeric_limits<int>::max())
      cout << d << endl;
    else
      cout << "?\n";
  }
  return 0;
}

UVa 11709 - Trust groups

Accepted date: 2014-06-07
Ranking (as of 2014-06-07): 15 out of 643
Language: C++

/*
  UVa 11709 - Trust groups

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11709_Trust_groups.cpp
*/

#include <vector>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int p_max = 1000, nr_name_chars_max = 31;
struct person {
  char name_[nr_name_chars_max + 1];
} persons[p_max];

void dfs1(int i, vector< vector<int> >& edges, vector<bool>& visited,
  vector<int>& vstack) // depth-first seach for a directed graph
{
  stack<int> st;
  visited[i] = true;
  st.push(i);
  while (!st.empty()) {
    i = st.top();
    vector<int>& e = edges[i];
    bool pushed = false;
    for (int j = 0; j < e.size(); j++) {
      int k = e[j];
      if (!visited[k]) {
        visited[k] = true;
        st.push(k);
        pushed = true;
      }
      if (pushed)
        break;
    }
    if (!pushed) {
      st.pop();
      vstack.push_back(i);
    }
  }
}

void dfs2(int i, vector< vector<int> >& redges, vector<bool>& visited)
// depth-first search for the transposed graph
{
  stack<int> st;
  visited[i] = false;
  st.push(i);
  while (!st.empty()) {
    i = st.top();
    vector<int>& re = redges[i];
    bool pushed = false;
    for (int j = 0; j < re.size(); j++) {
      int k = re[j];
      if (visited[k]) {
        visited[k] = false;
        st.push(k);
        pushed = true;
      }
      if (pushed)
        break;
    }
    if (!pushed)
      st.pop();
  }
}

int compare_person(const void* p, const void* q)
{
  return strcmp(reinterpret_cast<const person*>(p)->name_,
    reinterpret_cast<const person*>(q)->name_);
}

int main()
{
  while (true) {
    int p, t;
    scanf("%d %d", &p, &t);
    while (getchar() != '\n') // discard the rest of the line
      ;
    if (!p && !t)
      break;
    for (int i = 0; i < p; i++)
      gets(persons[i].name_);
    qsort(persons, p, sizeof(person), compare_person);

    vector < vector<int> > edges(p); // edges of directed graph
    vector < vector<int> > redges(p); // edges of transposed graph
    vector<bool> visited(p, false);
    vector <int> vstack;
    while (t--) {
      person pu, pv;
      gets(pu.name_);
      gets(pv.name_);
      int u = reinterpret_cast<person*>(
        bsearch(&pu, persons, p, sizeof(person), compare_person)) - persons,
        v = reinterpret_cast<person*>(
        bsearch(&pv, persons, p, sizeof(person), compare_person)) - persons;
      edges[u].push_back(v);
      redges[v].push_back(u);
    }
    // calculate number of strongly connected components
    for (int i = 0; i < p; i++)
      if (!visited[i])
        dfs1(i, edges, visited, vstack);
    int nr_scc = 0;
    for (int i = vstack.size() - 1; i >= 0; i--)
      if (visited[vstack[i]]) {
        nr_scc++;
        dfs2(vstack[i], redges, visited);
      }
    printf("%d\n", nr_scc);
  }
  return 0;
}

UVa 11459 - Snakes and Ladders

Accepted date: 2014-06-05
Ranking (as of 2014-06-05): 279 out of 661
Language: C++

/*
  UVa 11459 - Snakes and Ladders

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11459_Snakes_and_Ladders.cpp
*/

#include <cstdio>

const int die_max = 6, nr_squares = 100, nr_players_max = 1000000;

int players[nr_players_max]; // players[i] is the current square # of i-th player
int squares[nr_squares + die_max];
  // squares[i] is the next square to advance for i-th (i > 0) square

int main()
{
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    int i, j, k;
    for (i = 1; i < nr_squares; i++)
      squares[i] = i;
    for ( ; i < nr_squares + die_max; i++)
      squares[i] = nr_squares;
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    for (i = 0; i < a; i++)
      players[i] = 1;
    for (i = 0; i < b; i++) {
      scanf("%d %d", &j, &k);
      squares[j] = k;
    }
    bool game_over = false;
    for (i = 0; i < c; i++) {
      scanf("%d", &j);
      if (!game_over) {
        int& p = players[i % a];
        if ((p = squares[p + j]) == nr_squares)
          game_over = true;
      }
    }
    for (i = 0; i < a; i++)
      printf("Position of player %d is %d.\n", i + 1, players[i]);
  }
  return 0;
}

UVa 957 - Popes

Accepted date: 2014-06-04
Ranking (as of 2014-06-04): 139 out of 534
Language: C++

/*
  UVa 957 - Popes

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_957_Popes.cpp
*/

#include <cstdio>

const int p_max = 100000;
int years[p_max];

int main()
{
  int y;
  while (scanf("%d", &y) != EOF) {
    int p, i, j, max_popes = 0, max_p, max_i, max_j;
    scanf("%d", &p);
    for (i = 0; i < p; i++)
      scanf("%d", &years[i]);
    if (p == 1) {
      max_popes = 1; max_i = max_j = 0;
    }
    else {
      i = j = 0;
      do {
        if (years[j] - years[i] < y)
          j++;
        else {
          if ((max_p = j - i) > max_popes) {
            max_popes = max_p;
            max_i = i; max_j = j - 1;
          }
          i++;
          if (j < i)
            j = i;
        }
      } while (j < p);
      if ((max_p = j - i) > max_popes) {
        max_popes = max_p;
        max_i = i; max_j = j - 1;
      }
    }
    printf("%d %d %d\n", max_popes, years[max_i], years[max_j]);
  }
  return 0;
}