oj.uz

Submission #527764

# Submission time Handle Problem Language Result Execution time Memory
527764 2022-02-18T08:52:32 Z 1ne Autobus (COCI22_autobus) C++14
15 / 70
 1000 ms 452 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<pair<int64_t,int64_t>>>adj(n);
for (int i = 0;i<m;++i){
	int64_t x,y,z;cin>>x>>y>>z;
	--x;
	--y;
	adj[x].push_back({y,z});
}
int k,q;cin>>k>>q;
function<bool(int,int,int64_t)> bfs = [&](int u,int v,int64_t mid){
	queue<pair<int64_t,pair<int64_t,int64_t>>>q;
	q.push({u,{0,0}});
	vector<set<pair<int64_t,int64_t>>>got(n);
	got[u].insert({0,0});
	while(!q.empty()){
		auto x = q.front();
		q.pop();
		if (x.first==v){
			return true;
		}
		for (auto y:adj[x.first]){
			auto ok = [&](){
				for (auto j:got[y.first]){
					if (j.first<y.second + x.second.first && j.second<=x.second.second + 1){
						return false;
					}
				}
				return true;
			};
			if (y.second + x.second.first<=mid && x.second.second + 1<=k && ok()){
				vector<pair<int64_t,int64_t>>temp;
				for (auto j:got[y.first]){
					if (j.first>=y.second + x.second.first && j.second>=x.second.second+1){
						temp.push_back(j);
					}
				}
				for (auto j:temp){
					got[y.first].erase(j);
				}
				got[y.first].insert({y.second + x.second.first,x.second.second+1});
				q.push({y.first,{y.second + x.second.first,x.second.second+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;}

Subtask #1
15.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 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 440 KB Output is correct
2 Correct 881 ms 340 KB Output is correct
3 Execution timed out 1081 ms 332 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 Correct 1 ms 204 KB Output is correct
7 Execution timed out 1091 ms 452 KB Time limit exceeded
8 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 Correct 1 ms 204 KB Output is correct
7 Correct 158 ms 440 KB Output is correct
8 Correct 881 ms 340 KB Output is correct
9 Execution timed out 1081 ms 332 KB Time limit exceeded
10 Halted 0 ms 0 KB -