oj.uz

Submission #527773

# Submission time Handle Problem Language Result Execution time Memory
527773 2022-02-18T09:13:40 Z 1ne Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 64724 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});
		}
	}
}


int 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;
			vector<pair<int64_t,int64_t>>temp;
			for (auto x:arr[j][i]){
				if (x.first<mindist){
					mindist = x.first;
				}
				else if (x.second<mink){
					mink = x.second;
				}
				else temp.push_back(x);
			}
			for (auto x:temp){
				arr[j][i].erase(x);
			}
			temp.clear();
			mindist=1e15;
			mink=1e15;
			for (auto x:arr[i][k]){
				if (x.first<mindist){
					mindist = x.first;
				}
				else if (x.second<mink){
					mink = x.second;
				}
				else temp.push_back(x);
			}
			for (auto x:temp){
				arr[i][k].erase(x);
			}
			for (auto x:arr[j][i]){
				for (auto y:arr[i][k]){
					if (x.second + y.second<=kk)
					arr[j][k].insert({x.first + y.first,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 1 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 6 ms 796 KB Output is correct
3 Correct 13 ms 1632 KB Output is correct
4 Correct 14 ms 1356 KB Output is correct
5 Correct 47 ms 4548 KB Output is correct
6 Correct 48 ms 4424 KB Output is correct
7 Correct 246 ms 15492 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 901 ms 64724 KB Output is correct
8 Execution timed out 1085 ms 42404 KB Time limit exceeded
9 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 0 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 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 6 ms 796 KB Output is correct
9 Correct 13 ms 1632 KB Output is correct
10 Correct 14 ms 1356 KB Output is correct
11 Correct 47 ms 4548 KB Output is correct
12 Correct 48 ms 4424 KB Output is correct
13 Correct 246 ms 15492 KB Output is correct
14 Correct 901 ms 64724 KB Output is correct
15 Execution timed out 1085 ms 42404 KB Time limit exceeded
16 Halted 0 ms 0 KB -