oj.uz

Submission #527790

# Submission time Handle Problem Language Result Execution time Memory
527790 2022-02-18T09:35:08 Z 1ne Autobus (COCI22_autobus) C++14
0 / 70
 1000 ms 484 KB 
#include<bits/stdc++.h>
using namespace std;
struct points{
	int node,dist,kk;
	bool operator<(const points& y) const {
		if (dist == y.dist){
			return y.kk>kk;
		}
		return y.dist>dist;
	}
};
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);
}
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]});
			}
		}
	}
}
int k,q;cin>>k>>q;
function<bool(int,int,int64_t)> bfs = [&](int u,int v,int64_t mid){
	queue<points>q;
	q.push({u,0,0});
	vector<vector<bool>>visited(n,vector<bool>(n,false));
	while(!q.empty()){
		auto x = q.front();
		q.pop();
		if (x.node==v){
			return true;
		}
		for (auto y:adj[x.node]){
			if (visited[x.node][y.first])continue;
			if (y.second + x.dist<=mid && x.kk + 1<=k){
				visited[x.node][y.first]=true;
				q.push({y.first,y.second + x.dist,x.kk+1});
			}
		}
	}
	return false;
};
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;
	int64_t left = 1,right = 1e12;
	while(left<=right){
		int64_t mid = (left + right)>>1;
		if (bfs(x,y,mid)){
			right = mid - 1;
			ans = min(ans,mid);
		}
		else left = mid + 1;
	}
	if (ans ==1e15){
		cout<<-1<<'\n';
	}
	else 
	cout<<ans<<'\n';
}
return 0;}

Compilation message

Main.cpp: In lambda function:
Main.cpp:49:15: warning: narrowing conversion of 'y.std::pair<long int, long int>::first' from 'long int' to 'int' [-Wnarrowing]
   49 |     q.push({y.first,y.second + x.dist,x.kk+1});
      |             ~~^~~~~
Main.cpp:49:30: warning: narrowing conversion of '(y.std::pair<long int, long int>::second + ((long int)x.points::dist))' from 'long int' to 'int' [-Wnarrowing]
   49 |     q.push({y.first,y.second + x.dist,x.kk+1});
      |                     ~~~~~~~~~^~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 368 KB Output is correct
2 Correct 905 ms 484 KB Output is correct
3 Execution timed out 1055 ms 460 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -