Submission #1734850


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;
 
const int MAX_N = 2510;
using TYPE = ll; // 距離の型を入れる
vector<pair<ll, TYPE> > G[MAX_N];
vector<TYPE> dijkstra(int start){
	vector<TYPE> dist(MAX_N, INFF);
	dist[start] = 0;//dist[i] := start->iまでの最短距離
	priority_queue<pair<TYPE, int>, vector<pair<TYPE, int> >, greater<pair<TYPE, int> > >  que;
	que.push(make_pair(0, start));
	while(!que.empty()){
		TYPE cost; int u;//今までにかかった時間 現在の頂点
		cost = que.top().first, u = que.top().second;
		que.pop();
		if(dist[u] < cost) continue;
		for (auto tmp : G[u]){
			int v = tmp.first; TYPE time = tmp.second;//隣接する頂点 その頂点まで行く時間
			if(dist[v] > dist[u] + time){//u->v
				dist[v] = dist[u] + time;
				que.push(make_pair(dist[v], v));
			}
		}
	}
	return dist;
}
 
int N, M, R, T;
int main(void) {
	scanf("%d %d %d %d", &N, &M, &R, &T);
	rep(i, M) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c);
		a--; b--;
		G[a].pb(mp(b, c)), G[b].pb(mp(a, c));
	}
 
	ll ans = 0;
	rep(i, N) { // ゴールの位置
		auto dist = dijkstra(i);
		vector<double> vr, vt; // うさぎ かめ
		rep(j, N) {
			if(i == j) continue;
			vr.push_back((double)dist[j] / (double)R);
			vt.push_back((double)dist[j] / (double)T);
			if(dist[j] / R == dist[j] / T) ans--;
		}
		sort(all(vr)), sort(all(vt));

		for(auto k : vt) { // かめ
			// printf("t %f\n", k);
			ll cnt = (N - 1) - (upper_bound(all(vr), k) - vr.begin());
			// printf("cnt %d\n", cnt);
			ans += cnt;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User mmxsrup
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2276 Byte
Status WA
Exec Time 1503 ms
Memory 512 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &N, &M, &R, &T);
                                      ^
./Main.cpp:51:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d %d %d", &a, &b, &c);
                                             ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 1
WA × 1
AC × 4
WA × 14
Set Name Test Cases
Sample subtask0_sample-01.txt, subtask0_sample-02.txt
All subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt
Case Name Status Exec Time Memory
subtask0_sample-01.txt AC 1 ms 256 KB
subtask0_sample-02.txt WA 1 ms 384 KB
subtask1_01.txt WA 1 ms 384 KB
subtask1_02.txt WA 1 ms 384 KB
subtask1_03.txt WA 1 ms 384 KB
subtask1_04.txt WA 1 ms 384 KB
subtask1_05.txt AC 9 ms 384 KB
subtask1_06.txt AC 10 ms 384 KB
subtask1_07.txt WA 32 ms 512 KB
subtask1_08.txt AC 44 ms 384 KB
subtask1_09.txt WA 433 ms 512 KB
subtask1_10.txt WA 442 ms 512 KB
subtask1_11.txt WA 171 ms 512 KB
subtask1_12.txt WA 1430 ms 512 KB
subtask1_13.txt WA 1425 ms 512 KB
subtask1_14.txt WA 1502 ms 512 KB
subtask1_15.txt WA 1003 ms 512 KB
subtask1_16.txt WA 1503 ms 512 KB