oj.uz

Submission #878109

# Submission time Handle Problem Language Result Execution time Memory
878109 2023-11-24T05:38:02 Z arashMLG Toll (BOI17_toll) C++17
10 / 100
 1202 ms 5836 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

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

const int N = 5e4 + 23;
const int inf = 2e9;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int n,m,q,k;
int beg[N],en[N];
vector<pair<pii,int>> edges;
int dist[N];
map<pii,int> mp;

int get(int a,int b) {
	if(a > b) return -1;
	if(a ==b) return 0;
	if(beg[a] == -1 || en[b] == -1) return -1;
	if(mp[{a,b}] != 0) return mp[{a,b}];
	fill(dist+a+1, dist+b+1,inf);
	dist[a] = 0;
	for(int i = beg[a]; i <= en[b]; i ++) {
		auto [e,w] = edges[i];
		dist[e.S] = min(dist[e.S],dist[e.F] +w); 
	}
	mp[{a,b}] = (dist[b] >= inf ? -1 : dist[b]);
	return mp[{a,b}];
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>k>>n>>m>>q;
	for(int i = 0 ;i < m ;i ++) {
		int x,y,w;cin>>x>>y>>w;
		edges.pb({{x,y},w});
	}
	sort(all(edges));
	int i = 0;
	for(auto [e,_] : edges) {
		auto [x,y] = e;
		if(beg[x] == -1) beg[x] =i;
		en[y] = i;
		i++;
	}
	while(q--) {
		int a,b; cin>>a>>b;
		cout<< get(a,b) << '\n';
	}
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1202 ms 3296 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 1186 ms 2768 KB Output is correct
9 Correct 811 ms 2780 KB Output is correct
10 Runtime error 1 ms 740 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 3776 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 6 ms 604 KB Output is correct
9 Correct 847 ms 3688 KB Output is correct
10 Correct 820 ms 4800 KB Output is correct
11 Correct 843 ms 3780 KB Output is correct
12 Correct 505 ms 3348 KB Output is correct
13 Correct 267 ms 5836 KB Output is correct
14 Correct 182 ms 3028 KB Output is correct
15 Correct 145 ms 2876 KB Output is correct
16 Correct 145 ms 2768 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1202 ms 3296 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 1186 ms 2768 KB Output is correct
9 Correct 811 ms 2780 KB Output is correct
10 Runtime error 1 ms 740 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -