QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#346660 | #4779. Train delays | PetroTarnavskyi# | WA | 110ms | 12216kb | C++20 | 2.6kb | 2024-03-08 20:51:44 | 2024-03-08 20:51:44 |
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 long 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, n)
{
cntCon[i] = 0;
}
FOR (i, 0, 2 * n + 2)
{
FOR (j, 0, HOUR)
{
cons[i][j].clear();
d[i][j] = INF;
}
}
}
int add(string& s)
{
if (!mp.count(s))
mp[s] = SZ(mp);
return mp[s];
}
void solve()
{
string start, end;
cin >> start >> end;
int n;
cin >> n;
clear(n);
int st = add(start);
int en = add(end);
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5840kb
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.300000000000000 IMPOSSIBLE 305.053285714285713
result:
ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 110ms
memory: 12216kb
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.300000000000000 305.053285714285713 10.000000000000000 4.600000000000000 293.200000000000001 6.000000000000000 23.900000000000001 32.000000000000000 22.000000000000000 144.200000000000001 59.010000000000000 2.000000000000000 IMPOSSIBLE 33000053.057868572983352 1400.240207259722349 139.63000000000...
result:
wrong answer (test case 3)