Submission #12096

#	Time	Username	Problem	Language	Result	Execution time	Memory
12096		ainu7	Min-cost GCD (GA9_mcg)	C++98	57 / 100	1000 ms	1720 KiB

mcg

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

struct state {
  long long a, b, cost;
  state(long long _a, long long _b, long long _cost) {
    cost = _cost;
    a = _a;
    b = _b;
  };
  bool operator < (const state & another) const {
    if (cost != another.cost) return cost < another.cost;
    if (a != another.a) return a < another.a;
    return b < another.b;
  }
};

int main()
{
  int T;
  cin >> T;
  for (int i=0; i<T; i++) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    set<state> S;
    S.insert(state(a, b, 0));
    long long res = 1LL<<62;

    set<pair<long long, long long> > seen;

    while (1) {
      set<state>::iterator it = S.begin();
      state now = *it;
      S.erase(it);
      if (seen.find(pair<long long, long long>(now.a, now.b)) != seen.end()) continue;
      seen.insert(pair<long long, long long>(now.a, now.b));

      if (now.a == 0 || now.b == 0) {
        res = now.cost;
        break;
      }

      S.insert(state(now.b, now.a%now.b, now.cost+p));
      if (now.a >= now.b) {
        long long c = now.a / now.b;
        if (1.0*c*q < (1LL<<62))
          S.insert(state(now.a%now.b, now.b, now.cost+c*q));
      } else {
        long long c = now.b / now.a;
        if (1.0*c*q < (1LL<<62)) {
          S.insert(state(now.a, now.b%now.a, now.cost+c*q));
        }
      }
    }

    cout << res << endl;
  }
}

• Subtask 1: 14 / 14
• Subtask 2: 16 / 16
• Subtask 3: 27 / 27
• Subtask 4: 0 / 43