QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#366764 | #7849. Journey of Recovery | kevinyang | AC ✓ | 1698ms | 314860kb | C++17 | 3.3kb | 2024-03-25 07:20:26 | 2024-03-25 07:20:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gettime(string s){
int cur = 0;
for(int i = 0; i<s.size(); i++){
if(s[i]=='d'){
cur+=stoll(s.substr(0,i))*24*60;
}
if(s[i]==':'){
cur+=stoll(s.substr(i-2,2))*60;
cur+=stoll(s.substr(i+1));
}
}
return cur*10;
}
const int mxn = 4000005;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int m;
cin >> m;
int n = 0;
map<string,int>hm;
vector<vector<int>>arr(m,vector<int>(4));
vector<int>used(mxn);
for(int i = 0; i<m; i++){
string a,b,c,d;
cin >> a >> b >> c >> d;
if(!hm.count(a)){
n++;
hm[a] = n;
}
arr[i][0] = hm[a];
int t1 = gettime(b);
arr[i][1] = t1;
if(!hm.count(c)){
n++;
hm[c] = n;
}
arr[i][2] = hm[c];
int t2 = gettime(d);
arr[i][3] = t2;
/*
for(int j = 0; j<4; j++){
cerr << arr[i][j] << ' ';
}
cerr << '\n';
*/
}
vector<vector<int>>times(n+1);
int q;
cin >> q;
vector<int>edges(q);
for(int i = 0; i<q; i++){
cin >> edges[i];
edges[i]--;
used[edges[i]] = 1;
}
//cerr << "gay\n";
for(int i = 0; i<m; i++){
times[arr[i][0]].push_back(arr[i][1]+ (1^used[i]));
times[arr[i][2]].push_back(arr[i][3]);
}
vector<vector<pair<int,int>>>adj(mxn);
int curnode = 0;
map<pair<int,int>,int>mp;
//cerr << "gay\n";
for(int i = 1; i<=n; i++){
set<int>s;
for(int nxt: times[i]){
s.insert(nxt);
}
times[i].clear();
for(int nxt: s){
times[i].push_back(nxt);
curnode++;
mp[{i,nxt}] = curnode;
}
for(int j = 1; j<times[i].size(); j++){
int y = mp[{i,times[i][j]}];
int x = mp[{i,times[i][j-1]}];
int w = times[i][j]-times[i][j-1];
adj[y].push_back({w,x});
}
}
//cerr << "gay\n";
vector<int>ends;
for(int i = 0; i<m; i++){
int x = mp[{arr[i][0],arr[i][1]+(1^used[i])}];
int y = mp[{arr[i][2],arr[i][3]}];
int w = arr[i][3] - arr[i][1];
adj[y].push_back({w,x});
if(arr[edges[q-1]][2] == arr[i][2]){
ends.push_back(y);
}
/*
for(int j = 0; j<4; j++){
cerr << arr[i][j] << ' ';
}
cerr << '\n';
*/
}
vector<int>dis(mxn,(int)1e18);
vector<bool>vis(mxn);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
for(int nxt: ends){
pq.push({0,nxt});
dis[nxt] = 0;
}
//cerr << "gay\n";
while(pq.size()){
auto [d,cur] = pq.top(); pq.pop();
if(vis[cur])continue;
vis[cur] = true;
for(pair<int,int>nxt: adj[cur]){
if(dis[nxt.second] > nxt.first + d){
dis[nxt.second] = nxt.first+d;
pq.push({dis[nxt.second],nxt.second});
}
}
}
/*
for(int i = 1; i<=n; i++){
for(int nxt: times[i])cout << nxt << ' ';
cout << '\n';
}
for(int i = 1; i<=30; i++){
cout << dis[i] << ' ';
}
cout << '\n';
*/
int ans = 0;
for(int i = 0; i<q; i++){
int u = arr[edges[i]][0];
int start = arr[edges[i]][1];
if(u==arr[edges[q-1]][2])continue;
auto it = upper_bound(times[u].begin(),times[u].end(),start);
if(it == times[u].end()){
ans = (int)1e18;
//cout << "gay" << '\n';
break;
}
int node = mp[{u,*it}];
//cout << dis[node] + *it - arr[edges[q-1]][3] << '\n';
ans = max(ans,dis[node] + *it - arr[edges[q-1]][3]);
}
if(ans > (int)1e15){
cout << "stranded\n";
return 0;
}
cout << ans/10 << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 15ms
memory: 159924kb
input:
8 egnx 0d00:10 delft 0d01:00 delft 0d01:00 zad 0d09:00 zad 0d09:01 prg 0d15:30 prg 0d20:00 delft 1d02:15 prg 0d22:00 delft 1d04:15 zad 2d00:00 delft 3d00:00 egnx 2d00:00 delft 2d02:00 egnx 2d00:00 delft 2d02:00 4 1 2 3 4
output:
2745
result:
ok single line: '2745'
Test #2:
score: 0
Accepted
time: 23ms
memory: 159952kb
input:
3 ork 101d00:00 noc 101d00:01 ork 100d23:59 noc 101d00:02 dub 100d00:00 ork 101d00:00 2 3 1
output:
stranded
result:
ok single line: 'stranded'
Test #3:
score: 0
Accepted
time: 12ms
memory: 159872kb
input:
2 lax 0d00:30 hnl 0d06:20 lax 0d00:30 hnl 0d06:20 1 2
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 7ms
memory: 159940kb
input:
20 baa 0d00:31 bab 0d00:32 baa 0d00:15 bab 0d00:53 baa 0d00:44 bab 0d00:47 baa 0d00:11 bab 0d00:42 baa 0d00:15 bab 0d00:27 baa 0d00:19 bab 0d00:20 baa 0d00:16 bab 0d00:40 baa 0d00:07 bab 0d00:54 baa 0d00:25 bab 0d00:44 baa 0d00:32 bab 0d00:42 bab 0d00:56 bac 0d01:17 bab 0d01:10 bac 0d01:20 bab 0d01:...
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 21ms
memory: 159920kb
input:
90 baa 0d00:06 bab 0d00:37 baa 0d00:49 bab 0d00:52 baa 0d00:05 bab 0d00:27 baa 0d00:26 bab 0d00:27 baa 0d00:03 bab 0d00:36 baa 0d00:23 bab 0d00:31 baa 0d00:01 bab 0d00:55 baa 0d00:39 bab 0d00:42 baa 0d00:28 bab 0d00:44 baa 0d00:04 bab 0d00:38 bab 0d01:20 bac 0d01:35 bab 0d01:45 bac 0d01:52 bab 0d01:...
output:
21
result:
ok single line: '21'
Test #6:
score: 0
Accepted
time: 7ms
memory: 160092kb
input:
7 bac 3d00:06 bab 39d22:17 bab 74d04:02 baa 81d19:39 baa 12d18:01 bab 86d01:31 baa 48d07:23 bac 67d05:42 bac 34d21:56 bab 50d08:26 bac 0d05:31 baa 1d05:40 bac 0d01:38 baa 0d15:10 1 7
output:
870
result:
ok single line: '870'
Test #7:
score: 0
Accepted
time: 20ms
memory: 160004kb
input:
17 bac 74d16:04 bae 98d19:52 bad 8d22:44 bab 12d05:58 bac 13d19:03 bae 77d05:09 baa 65d12:55 bad 98d21:21 baa 44d00:55 bae 85d14:23 bab 16d16:49 baa 82d09:17 bac 22d11:24 baa 56d11:42 bad 52d19:22 bab 95d14:48 bac 87d05:01 bae 99d06:27 bad 11d00:59 bae 40d23:57 bad 49d23:49 bac 51d04:56 bab 87d16:37...
output:
121500
result:
ok single line: '121500'
Test #8:
score: 0
Accepted
time: 19ms
memory: 160676kb
input:
1292 bda 27d03:01 bbh 84d17:32 bdd 29d08:34 bdg 79d12:41 beb 58d02:11 bdh 83d03:09 bcd 25d22:40 bdj 54d04:08 bbf 61d05:55 bbi 66d03:11 bbf 55d17:45 bcj 69d08:21 bcf 77d08:04 bea 97d14:00 bah 67d00:16 bbc 68d00:51 bdj 33d00:22 bcd 78d09:32 bej 33d00:36 beb 74d23:07 bee 44d05:33 bdc 54d14:34 bbc 11d04...
output:
stranded
result:
ok single line: 'stranded'
Test #9:
score: 0
Accepted
time: 24ms
memory: 161720kb
input:
5084 bfi 30d16:18 bhb 53d00:34 bhb 13d00:48 bee 35d05:13 bdf 31d15:19 bda 51d18:11 bgi 85d12:26 bjj 87d17:41 bdi 81d19:03 bdf 97d21:24 bbj 35d13:39 bda 57d08:21 bbf 9d01:40 baj 91d13:52 bhc 30d03:05 bfd 96d00:19 bbh 82d22:44 bbd 91d21:34 bhe 18d20:16 bje 85d17:38 bad 45d03:58 bag 98d00:20 bba 33d04:...
output:
71921
result:
ok single line: '71921'
Test #10:
score: 0
Accepted
time: 1698ms
memory: 314860kb
input:
500834 gfg 51d23:48 jhh 90d07:46 iee 39d21:18 cga 71d19:14 dha 86d16:25 hih 97d06:29 gef 20d02:03 djj 90d15:23 bgb 12d20:08 bjc 15d23:38 cgc 17d02:37 ede 94d06:39 cjj 47d10:47 fbb 93d23:36 cjf 61d20:43 hba 74d15:30 ibe 27d14:46 ice 57d22:24 cgj 57d08:11 hdc 63d17:09 hcj 28d08:25 ghe 51d14:40 hcf 33d...
output:
stranded
result:
ok single line: 'stranded'
Test #11:
score: 0
Accepted
time: 39ms
memory: 163132kb
input:
9990 baa 0d00:49 bab 0d00:51 baa 0d00:35 bab 0d00:36 baa 0d00:20 bab 0d00:34 baa 0d00:01 bab 0d00:03 baa 0d00:35 bab 0d00:41 baa 0d00:30 bab 0d00:43 baa 0d00:09 bab 0d00:59 baa 0d00:12 bab 0d00:42 baa 0d00:10 bab 0d00:27 baa 0d00:43 bab 0d00:44 bab 0d00:26 bac 0d00:46 bab 0d00:41 bac 0d00:58 bab 0d0...
output:
stranded
result:
ok single line: 'stranded'
Test #12:
score: 0
Accepted
time: 164ms
memory: 189260kb
input:
99990 baa 0d00:07 bab 0d00:23 baa 0d00:45 bab 0d00:47 baa 0d00:07 bab 0d00:42 baa 0d00:04 bab 0d00:32 baa 0d00:15 bab 0d00:46 baa 0d00:14 bab 0d00:40 baa 0d00:10 bab 0d00:29 baa 0d00:01 bab 0d00:45 baa 0d00:18 bab 0d00:22 baa 0d00:06 bab 0d00:45 bab 0d00:45 bac 0d01:01 bab 0d00:59 bac 0d01:05 bab 0d...
output:
stranded
result:
ok single line: 'stranded'