oj.uz

Submission #527801

# Submission time Handle Problem Language Result Execution time Memory
527801 2022-02-18T10:30:07 Z 1ne Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 4904 KB 
#include<bits/stdc++.h>
using namespace std;
struct points{
	int64_t node,dist,kk;
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;cin>>n>>m;
vector<vector<pair<int64_t,int64_t>>>adj(n);
vector<vector<int64_t>>dist(n,vector<int64_t>(n,1e15));
//vector<vector<vector<pair<int64_t,int64_t>>>>arr(n,vector<vector<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);
}
int k,q;cin>>k>>q;
k = min(k,n*n);
vector<vector<vector<int64_t>>>distt(n,vector<vector<int64_t>>(n,vector<int64_t>(k+1,1e15)));
for (int i = 0;i<n;++i){
	for (int j =0;j<n;++j){
		if (i!=j){
			if (dist[i][j]!=1e15){
				adj[i].push_back({j,dist[i][j]});
			}
		}
	}
}
function<void(int)> bfs = [&](int u){
	queue<points>q;
	q.push({u,0,0});
	while(!q.empty()){
		auto v = q.front();
		q.pop();
		for (auto x:adj[v.node]){
			if (v.kk+1<=k&&distt[u][x.first][v.kk+1]>x.second + v.dist){
				distt[u][x.first][v.kk+1] = x.second + v.dist;
				q.push({x.first,x.second + v.dist,v.kk + 1});
			}
		}
	}
};
for (int i = 0;i<n;++i){
	bfs(i);
}
for (int i = 0;i<q;++i){
	int x,y;cin>>x>>y;
	--x;
	--y;
	if (x==y){
		cout<<0<<'\n';
		continue;
	}
	int64_t ans = 1e15;
	for (int i = 0;i<=k;++i){
		ans = min(distt[x][y][i],ans);
	}
	if (ans==1e15){
		cout<<"-1"<<'\n';
	}
	else cout<<ans<<'\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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 8 ms 808 KB Output is correct

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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 221 ms 1768 KB Output is correct
8 Execution timed out 1093 ms 4904 KB Time limit exceeded
9 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 3 ms 716 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 8 ms 808 KB Output is correct
14 Correct 221 ms 1768 KB Output is correct
15 Execution timed out 1093 ms 4904 KB Time limit exceeded
16 Halted 0 ms 0 KB -