oj.uz

Submission #533478

# Submission time Handle Problem Language Result Execution time Memory
533478 2022-03-06T06:46:16 Z Slavita Autobus (COCI22_autobus) C++14
15 / 70
 1000 ms 1108 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ve vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define si(v) (int)v.size()
#define en '\n'
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_muiltiset tree<int, null_type,less_equal<>, rb_tree_tag,tree_order_statistics_node_update>
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e3 + 228;
const int big = 1e9 + 228;
const ll llbig = 1e18 + 228;
//ordered_set os; // os.order_of_key(4), (*os.find_by_order(5))
ll n, m, ans, k, q, d[N][N], mem[N][N];
priority_queue<pair<pair<ll, ll>, ll>> Q;

//#undef int
int main(){
    //#define int long long
    iostream::sync_with_stdio(false); cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        ll a, b, t;
        cin >> a >> b >> t;
        if (mem[a][b] == 0) mem[a][b] = t;
        else mem[a][b] = min(mem[a][b], t);
    }

    cin >> k >> q;
    while(q--){
        ll start, finish;
        cin >> start >> finish;
        Q.push({{0, 0}, start});

        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= n; j++) d[i][j] = llbig;
        d[start][0] = 0;

        while(!Q.empty()){
            ll v = Q.top().se;
            ll time = -Q.top().fi.fi;
            ll kol = -Q.top().fi.se;
            Q.pop();

            if (kol > k) {continue;}

            for (int u = 1; u <= n; u++){
                ll c = mem[v][u];
                if (!c) continue;
                if (d[u][kol + 1] < time + c) continue;
                d[u][kol + 1] = time + c;
                Q.push({{-time-c, -kol-1}, u});
            }
        }

        ll mn = llbig;
        for (int i = 0; i <= k; i++) mn = min(mn, d[finish][i]);
        cout << (mn == llbig ? -1 : mn) << en;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 976 KB Output is correct
2 Correct 110 ms 976 KB Output is correct
3 Correct 263 ms 1096 KB Output is correct
4 Correct 321 ms 992 KB Output is correct
5 Correct 667 ms 1108 KB Output is correct
6 Correct 596 ms 972 KB Output is correct
7 Execution timed out 1084 ms 992 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Execution timed out 1082 ms 1024 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 43 ms 976 KB Output is correct
8 Correct 110 ms 976 KB Output is correct
9 Correct 263 ms 1096 KB Output is correct
10 Correct 321 ms 992 KB Output is correct
11 Correct 667 ms 1108 KB Output is correct
12 Correct 596 ms 972 KB Output is correct
13 Execution timed out 1084 ms 992 KB Time limit exceeded
14 Halted 0 ms 0 KB -