QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#366764#7849. Journey of RecoverykevinyangAC ✓1698ms314860kbC++173.3kb2024-03-25 07:20:262024-03-25 07:20:26

Judging History

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

  • [2024-03-25 07:20:26]
  • 评测
  • 测评结果:AC
  • 用时:1698ms
  • 内存:314860kb
  • [2024-03-25 07:20:26]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'