QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#346648 | #4779. Train delays | PetroTarnavskyi# | WA | 44ms | 11240kb | C++20 | 2.5kb | 2024-03-08 20:25:45 | 2024-03-08 20:25:46 |
Judging History
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)