QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#346648#4779. Train delaysPetroTarnavskyi#WA 44ms11240kbC++202.5kb2024-03-08 20:25:452024-03-08 20:25:46

Judging History

你现在查看的是最新测评结果

  • [2024-03-08 20:25:46]
  • 评测
  • 测评结果:WA
  • 用时:44ms
  • 内存:11240kb
  • [2024-03-08 20:25:45]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

struct Connection
{
	int a, b;
	int m, t, p, d;
};

const int N = 1047;

map<string, int> mp;
Connection c[N];
VI cons[2 * N][60];
int cntCon[N];
const db INF = 1e9 + 47;
const int HOUR = 60;
db d[2 * N][60];

void clear(int n)
{
	mp.clear();
	FOR (i, 0, 2 * n)
		FOR (j, 0, HOUR)
			cons[i][j].clear();
}

int add(string& s)
{
	if (!mp.count(s))
		mp[s] = SZ(mp);
	return mp[s];
}

void solve()
{
	string start, end;
	cin >> start >> end;
	int st = add(start);
	int en = add(end);
	
	int n;
	cin >> n;
	
	FOR (i, 0, 2 * n) FOR (j, 0, HOUR) d[i][j] = INF;
	
	FOR (i, 0, n)
	{
		string s1, s2;
		cin >> s1 >> s2 >> c[i].m >> c[i].t >> c[i].p >> c[i].d;
		c[i].a = add(s1);
		c[i].b = add(s2);
		int t = c[i].m + c[i].t;
		cons[c[i].b][t % HOUR].PB(i);
		cntCon[i]++;
		FOR (j, 1, c[i].d + 1)
		{
			cons[c[i].b][(t + j) % HOUR].PB(i);
			cntCon[i]++;
		}
	}
	set<pair<db, PII>> s;
	FOR (i, 0, HOUR)
	{
		d[en][i] = 0;
		s.insert({0, {en, i}});
	}
	while (!s.empty())
	{
		auto [dis, p] = *s.begin();
		s.erase(s.begin());
		auto [v, t] = p;
		auto& cp = d[v][(t - 1 + HOUR) % HOUR]; 
		if (cp > dis + 1)
		{
			s.erase({cp, {v, (t - 1 + HOUR) % HOUR}});
			cp = dis + 1;
			s.insert({cp, {v, (t - 1 + HOUR) % HOUR}});
		}
		for (auto i : cons[v][t])
		{
			cntCon[i]--;
			if (cntCon[i] == 0)
			{
				int T = c[i].m + c[i].t;
				db prob = c[i].p / 100.0; 
				db sum = (1 - prob) * (c[i].t + d[c[i].b][T % HOUR]);
				FOR (add, 1, c[i].d + 1)
				{
					sum += (prob / c[i].d) * (c[i].t + add + d[c[i].b][(T + add) % HOUR]);
				}
				if (d[c[i].a][c[i].m] > sum)
				{
					s.erase({d[c[i].a][c[i].m], {c[i].a, c[i].m}});
					d[c[i].a][c[i].m] = sum;
					s.insert({d[c[i].a][c[i].m], {c[i].a, c[i].m}});
				}
			}
		}
	}
	
	db ans = INF;
	FOR (i, 0, HOUR)
		ans = min(ans, d[st][i]);
	if (ans + 47 > INF)
		cout << "IMPOSSIBLE\n";
	else
	{
		cout << ans << '\n';
	}
	clear(n);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3848kb

input:

3
Hamburg Bremen
3
Hamburg Bremen 15 68 10 5
Hamburg Bremen 46 55 50 60
Bremen Frankfurt 14 226 10 120
Amsterdam Rotterdam
1
Amsterdam Utrecht 10 22 5 10
BremenVegesack Utrecht
9
BremenVegesack BremenHbf 15 10 0 1
BremenVegesack BremenHbf 45 10 0 1
BremenVegesack Leer 23 140 10 15
BremenHbf Osnabruc...

output:

68.299999999999997
IMPOSSIBLE
305.053285714285721

result:

ok  (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 44ms
memory: 11240kb

input:

76
Hamburg Bremen
3
Hamburg Bremen 15 68 10 5
Hamburg Bremen 46 55 50 60
Bremen Frankfurt 14 226 10 120
BremenVegesack Utrecht
9
BremenVegesack BremenHbf 15 10 0 1
BremenVegesack BremenHbf 45 10 0 1
BremenVegesack Leer 23 140 10 15
BremenHbf Osnabruck 44 51 60 70
Osnabruck Amersfoort 55 147 38 40
Am...

output:

68.299999999999997
305.053285714285721
3.600000000000000
4.600000000000000
293.200000000000045
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
63.000000000000000
175.250000000000028
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
325.011428571428780
202.474999999999994
300.120000000000118
551.43370326276351...

result:

wrong answer  (test case 3)