AtCoder Regular Contest 008

Submission #1046413

Source codeソースコード

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}

// cout deque
template<typename T> ostream& operator<<(ostream& s, const deque<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) { s << vv[i]; }
  return s;
}

// cout 2-dimentional deque
template<typename T> ostream& operator<<(ostream& s, const deque< deque<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) { s << vv[i]; }
  return s;
}

#define INF DBL_MAX/4

int n;
vv<double> cost;
vector<double> d; // 仮のコストの最小値、最終結果
deque<bool> used;

void dijkstra(int s) {
  d.assign(n, INF);
  used.assign(n, false);
  d[s] = 0;

  while (true) {
    int v = -1;
    rep (u, n) {
      if (!used[u] && (v == -1 || d[u] < d[v])) {
        v = u;
      }
    }
    if (v == -1) {
      break;
    }
    used[v] = true;
    rep (u, n) {
      d[u] = min(d[u], d[v] + cost[v][u]);
    }
  }
}

int main() {
  scanf("%d", &n);
  vector<double> x(n), y(n), t(n), r(n);
  rep (i, n) {
    scanf("%lf %lf %lf %lf", &x[i], &y[i], &t[i], &r[i]);
  }
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  cost.assign(n, vector<double>(n, INF));
  rep (i, n) {
    double dx;
    double dy;
    double dist;
    double vij;
    double vji;

    rep (j, n) {
      if (i == j) {
        continue;
      }
      dx = x[i] - x[j];
      dy = y[i] - y[j];
      dist = sqrt(dx*dx + dy*dy);
      vij = min(t[i], r[j]);
      vji = min(t[j], r[i]);
      cost[i][j] = dist / vij;
      cost[j][i] = dist / vji;
    }
  }

  dijkstra(0);
  sort(all(d), greater<double>());
  rep (i, n-1) {
    d[i] += i;
  }
  sort(all(d), greater<double>());
  printf("%.9f\n", d[0]);

  return 0;
}

Submission

Task問題 C - THE☆たこ焼き祭り2012
User nameユーザ名 056 tspcx
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3106 Byte
File nameファイル名
Exec time実行時間 52 ms
Memory usageメモリ使用量 8740 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:100:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:103:57: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lf %lf %lf %lf", &x[i], &y[i], &t[i], &r[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 00_min.txt,00_sample_01.txt,00_sample_02.txt,00_sample_03.txt,00_sample_04.txt,00_sample_05.txt,01_rand_00.txt,01_rand_01.txt,01_rand_02.txt,01_rand_03.txt,01_rand_04.txt,01_rand_05.txt,01_rand_06.txt,01_rand_07.txt,01_rand_08.txt,01_rand_09.txt,02_maxrand_00.txt,02_maxrand_01.txt,02_maxrand_02.txt,02_maxrand_03.txt,02_maxrand_04.txt,02_maxrand_05.txt,02_maxrand_06.txt,02_maxrand_07.txt,02_maxrand_08.txt,02_maxrand_09.txt,03_slow_00.txt,03_slow_01.txt,03_slow_02.txt,03_slow_03.txt,03_slow_04.txt,03_slow_05.txt,03_slow_06.txt,03_slow_07.txt,03_slow_08.txt,03_slow_09.txt,04_logspeed_00.txt,04_logspeed_01.txt,04_logspeed_02.txt,04_logspeed_03.txt,04_logspeed_04.txt,04_logspeed_05.txt,04_logspeed_06.txt,04_logspeed_07.txt,04_logspeed_08.txt,04_logspeed_09.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_min.txt AC 18 ms 800 KB
00_sample_01.txt AC 19 ms 800 KB
00_sample_02.txt AC 18 ms 800 KB
00_sample_03.txt AC 19 ms 804 KB
00_sample_04.txt AC 17 ms 804 KB
00_sample_05.txt AC 19 ms 800 KB
01_rand_00.txt AC 20 ms 1052 KB
01_rand_01.txt AC 24 ms 2208 KB
01_rand_02.txt AC 35 ms 4772 KB
01_rand_03.txt AC 21 ms 1316 KB
01_rand_04.txt AC 22 ms 1564 KB
01_rand_05.txt AC 20 ms 1176 KB
01_rand_06.txt AC 23 ms 1948 KB
01_rand_07.txt AC 26 ms 2640 KB
01_rand_08.txt AC 18 ms 916 KB
01_rand_09.txt AC 33 ms 4516 KB
02_maxrand_00.txt AC 49 ms 8732 KB
02_maxrand_01.txt AC 49 ms 8608 KB
02_maxrand_02.txt AC 49 ms 8692 KB
02_maxrand_03.txt AC 49 ms 8696 KB
02_maxrand_04.txt AC 47 ms 8608 KB
02_maxrand_05.txt AC 48 ms 8604 KB
02_maxrand_06.txt AC 51 ms 8688 KB
02_maxrand_07.txt AC 49 ms 8568 KB
02_maxrand_08.txt AC 50 ms 8612 KB
02_maxrand_09.txt AC 50 ms 8732 KB
03_slow_00.txt AC 50 ms 8572 KB
03_slow_01.txt AC 48 ms 8696 KB
03_slow_02.txt AC 47 ms 8568 KB
03_slow_03.txt AC 51 ms 8688 KB
03_slow_04.txt AC 46 ms 8564 KB
03_slow_05.txt AC 48 ms 8608 KB
03_slow_06.txt AC 49 ms 8696 KB
03_slow_07.txt AC 49 ms 8652 KB
03_slow_08.txt AC 47 ms 8604 KB
03_slow_09.txt AC 52 ms 8688 KB
04_logspeed_00.txt AC 48 ms 8680 KB
04_logspeed_01.txt AC 49 ms 8740 KB
04_logspeed_02.txt AC 49 ms 8608 KB
04_logspeed_03.txt AC 50 ms 8612 KB
04_logspeed_04.txt AC 47 ms 8604 KB
04_logspeed_05.txt AC 49 ms 8740 KB
04_logspeed_06.txt AC 48 ms 8728 KB
04_logspeed_07.txt AC 49 ms 8696 KB
04_logspeed_08.txt AC 51 ms 8592 KB
04_logspeed_09.txt AC 49 ms 8612 KB