oj.uz

Submission #527800

# Submission time Handle Problem Language Result Execution time Memory
527800 2022-02-18T10:24:27 Z 1ne Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 3172 KB 
#include<bits/stdc++.h>
using namespace std;
struct points{
	int 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]});
				distt[i][j][1] = dist[i][j];
			}
		}
		else if (i==j){
			distt[i][j][0] = 0;
			distt[i][j][1] = 0;
		}
	}
}
function<void(int)> bfs = [&](int u){
	queue<int>q;
	q.push(u);
	while(!q.empty()){
		auto v = q.front();
		q.pop();
		for (auto x:adj[v]){
			bool ok=false;
			for (int j = 0;j<k;++j){
				if (distt[u][x.first][j+1]>distt[u][v][j] + x.second)ok=true;
				distt[u][x.first][j+1] = min(distt[u][v][j] + x.second,distt[u][x.first][j+1]);
			}
			if (ok)q.push(x.first);
		}
	}
};
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 0 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 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 8 ms 716 KB Output is correct
7 Correct 15 ms 716 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 0 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 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 34 ms 1488 KB Output is correct
8 Correct 240 ms 3172 KB Output is correct
9 Correct 5 ms 716 KB Output is correct
10 Correct 265 ms 2032 KB Output is correct
11 Correct 103 ms 988 KB Output is correct
12 Execution timed out 1093 ms 2380 KB Time limit exceeded
13 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 0 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 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 8 ms 716 KB Output is correct
13 Correct 15 ms 716 KB Output is correct
14 Correct 34 ms 1488 KB Output is correct
15 Correct 240 ms 3172 KB Output is correct
16 Correct 5 ms 716 KB Output is correct
17 Correct 265 ms 2032 KB Output is correct
18 Correct 103 ms 988 KB Output is correct
19 Execution timed out 1093 ms 2380 KB Time limit exceeded
20 Halted 0 ms 0 KB -