oj.uz

Submission #714560

# Submission time Handle Problem Language Result Execution time Memory
714560 2023-03-25T05:20:45 Z faribourz Toll (BOI17_toll) C++14
18 / 100
 3000 ms 5620 KB 
// Only GOD
// Believe in yourself!
// -o Sango zadam be shishe 
// -o Comeback bezan hamishe!
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

#define pb push_back
#define F first
#define S second
#define bit(x, y) (x >> y)&1
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define mid ((l+r)>>1)
#define lid (id << 1)
#define rid (lid | 1)

const int N = 5e4+10;
const int INF = 1e9+10;
int n, m, k, o;
vector<pii> query[N];
vector<pii> G[N];
int ans[N], dis[N];
set<int> s;
void dij(int v){
	priority_queue<pii> q;
	for(int i=0; i <= n; i++)
		dis[i] = INF;
	dis[v] = 0;
	q.push({0, v});
	while(!q.empty()){
		int a=q.top().S;
		q.pop();
		for(auto x : G[a]){
			if(dis[a] + x.S < dis[x.F]){
				dis[x.F] = dis[a] + x.S;
				q.push({-dis[x.F], x.F});
			}
		}
	}
}
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> k >> n >> m >> o;
	for(int i = 0; i < m; i++){
		int v, u, w;
		cin >> v >> u >> w;
		G[v].pb({u, w});
	}
	for(int i =1 ; i <= o; i++){
		int v, u;
		cin >> v >> u;
		query[v].pb({u, i});
		s.insert(v);
	}
	for(int u:s){
		dij(u);
		for(auto x : query[u]){
			ans[x.S] = dis[x.F];
		}
	}
	for(int i = 1;i  <= o; i++)
		cout << (ans[i] == INF ? -1 : ans[i]) << '\n';
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 5256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4684 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 4 ms 3028 KB Output is correct
9 Correct 19 ms 4692 KB Output is correct
10 Correct 49 ms 5620 KB Output is correct
11 Correct 43 ms 4692 KB Output is correct
12 Correct 29 ms 4604 KB Output is correct
13 Correct 57 ms 5504 KB Output is correct
14 Correct 35 ms 4472 KB Output is correct
15 Correct 29 ms 4088 KB Output is correct
16 Correct 26 ms 4128 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 2644 KB Output is correct
8 Correct 11 ms 2780 KB Output is correct
9 Correct 8 ms 2644 KB Output is correct
10 Correct 31 ms 4436 KB Output is correct
11 Correct 212 ms 4424 KB Output is correct
12 Correct 313 ms 5332 KB Output is correct
13 Correct 357 ms 5592 KB Output is correct
14 Correct 331 ms 4936 KB Output is correct
15 Correct 195 ms 4052 KB Output is correct
16 Correct 192 ms 4084 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 2644 KB Output is correct
8 Correct 11 ms 2780 KB Output is correct
9 Correct 8 ms 2644 KB Output is correct
10 Correct 31 ms 4436 KB Output is correct
11 Correct 212 ms 4424 KB Output is correct
12 Correct 313 ms 5332 KB Output is correct
13 Correct 357 ms 5592 KB Output is correct
14 Correct 331 ms 4936 KB Output is correct
15 Correct 195 ms 4052 KB Output is correct
16 Correct 192 ms 4084 KB Output is correct
17 Execution timed out 3056 ms 4564 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 5256 KB Time limit exceeded
2 Halted 0 ms 0 KB -