oj.uz

Submission #527777

# Submission time Handle Problem Language Result Execution time Memory
527777 2022-02-18T09:19:51 Z 1ne Autobus (COCI22_autobus) C++14
15 / 70
 1000 ms 81256 KB 
#include<bits/stdc++.h>
using namespace std;
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;cin>>n>>m;
vector<vector<int64_t>>dist(n,vector<int64_t>(n,1e15));
vector<vector<set<pair<int64_t,int64_t>>>>arr(n,vector<set<pair<int64_t,int64_t>>>(n));
for (int i = 0;i<m;++i){
	int64_t x,y,z;cin>>x>>y>>z;
	--x;
	--y;
	dist[x][y] = min(dist[x][y],z);
}
for (int i = 0;i<n;++i){
	for (int j = 0;j<n;++j){
		if (i!=j&&dist[i][j]!=1e15){
			arr[i][j].insert({dist[i][j],1});
		}
	}
}


int64_t kk,q;cin>>kk>>q;
for (int i = 0;i<n;++i){
	for (int j = 0;j<n;++j){
		for (int k = 0;k<n;++k){
			int64_t mindist = 1e15,mink=1e15;
			for (auto x:arr[j][k]){
				if (x.first<mindist){
					mindist = x.first;
				}
				if (x.second<mink){
					mink = x.second;
				}
			}
			for (auto x:arr[j][i]){
				int64_t mink = 1e15;
				for (auto y:arr[i][k]){
					if (x.second + y.second<=min(mink,kk)){
						arr[j][k].insert({x.first + y.first,x.second + y.second});
						mink = min(mink,x.second + y.second);
					}
				}
			}
		}
	}
}
for (int i = 0;i<q;++i){
	int x,y;cin>>x>>y;
	--x;
	--y;
	if (x==y){
		cout<<0<<'\n';
		continue;
	}
	if (arr[x][y].empty()){
		cout<<-1<<'\n';
	}
	else{
		auto z = *arr[x][y].begin();
		cout<<z.first<<'\n';
	}
}
return 0;}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 17 ms 1952 KB Output is correct
4 Correct 15 ms 1532 KB Output is correct
5 Correct 617 ms 12060 KB Output is correct
6 Correct 589 ms 9976 KB Output is correct
7 Execution timed out 1088 ms 30556 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Execution timed out 1090 ms 81256 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 17 ms 1952 KB Output is correct
10 Correct 15 ms 1532 KB Output is correct
11 Correct 617 ms 12060 KB Output is correct
12 Correct 589 ms 9976 KB Output is correct
13 Execution timed out 1088 ms 30556 KB Time limit exceeded
14 Halted 0 ms 0 KB -