oj.uz

Submission #628252

# Submission time Handle Problem Language Result Execution time Memory
628252 2022-08-13T08:58:19 Z duytuandao21 Toll (BOI17_toll) C++17
8 / 100
 3000 ms 51928 KB 
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define ii pair<ll, int>
#define task "test"

const int inf = 1e9 + 7;
const ll infll = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 2e6 + 3;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

int k,n,m,q;
vector<ii> adj[N];

void solve(int x,int y) {
    vector<ll> d(n+1, inf);
    d[x] = 0;
    priority_queue< ii, vector<ii>, greater<ii> > p;
    p.push(mp(0,x));
    while(!p.empty()) {
        int u = p.top().se;
        int val = p.top().fi; p.pop();
        if(val != d[u]) continue;
        for(ii X : adj[u]) {
            int v = X.se;
            int he = X.fi;
            if(d[v] > val + he) {
                d[v] = val + he;
                p.push(mp(d[v], v));
            }
        }
    }
    if(d[y] == inf) cout<<-1<<'\n'; else cout<<d[y]<<'\n';
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>k>>n>>m>>q;
	for(int i=1;i<=m;i++) {
        int u,v,w; cin>>u>>v>>w;
        adj[u].pb(mp(w,v));
        //adj[v].pb(mp(w,u));
	}
	while(q--) {
        int u,v;
        cin>>u>>v;
        solve(u,v);
	}
    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 24 ms 47280 KB Output is correct
3 Correct 25 ms 47188 KB Output is correct
4 Correct 25 ms 47188 KB Output is correct
5 Correct 23 ms 47188 KB Output is correct
6 Correct 24 ms 47288 KB Output is correct
7 Correct 31 ms 47296 KB Output is correct
8 Correct 34 ms 47412 KB Output is correct
9 Correct 32 ms 47376 KB Output is correct
10 Correct 46 ms 49152 KB Output is correct
11 Correct 253 ms 50140 KB Output is correct
12 Correct 396 ms 51592 KB Output is correct
13 Correct 425 ms 51928 KB Output is correct
14 Correct 326 ms 50856 KB Output is correct
15 Correct 230 ms 49484 KB Output is correct
16 Correct 237 ms 49504 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 24 ms 47280 KB Output is correct
3 Correct 25 ms 47188 KB Output is correct
4 Correct 25 ms 47188 KB Output is correct
5 Correct 23 ms 47188 KB Output is correct
6 Correct 24 ms 47288 KB Output is correct
7 Correct 31 ms 47296 KB Output is correct
8 Correct 34 ms 47412 KB Output is correct
9 Correct 32 ms 47376 KB Output is correct
10 Correct 46 ms 49152 KB Output is correct
11 Correct 253 ms 50140 KB Output is correct
12 Correct 396 ms 51592 KB Output is correct
13 Correct 425 ms 51928 KB Output is correct
14 Correct 326 ms 50856 KB Output is correct
15 Correct 230 ms 49484 KB Output is correct
16 Correct 237 ms 49504 KB Output is correct
17 Execution timed out 3089 ms 50308 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 3062 ms 49264 KB Time limit exceeded
2 Halted 0 ms 0 KB -