oj.uz

Submission #533472

# Submission time Handle Problem Language Result Execution time Memory
533472 2022-03-06T06:15:55 Z N1NT3NDO Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 420 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 75;
vector< pair<int, int> > g[N];
int n, m, q, k, F;
ll ans;

void dfs(int v, int skok, ll sum)
{
    if (skok > k || sum > ans) return;

    if (v == F)
    {
        ans = min(ans, sum);
        return;
    }

    for(auto [u, w] : g[v])
    {
        dfs(u, skok + 1, sum + w);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v, z;
        cin >> u >> v >> z;
        g[u].pb({v, z});
    }

    cin >> k >> q;

    while(q--)
    {
        int S;
        cin >> S >> F;
        ans = 1e18;

        dfs(S, 0, 0);

        if (ans == 1e18) cout << -1 << '\n';
        else cout << ans << '\n';
    }
}

Compilation message

Main.cpp: In function 'void dfs(int, int, long long int)':
Main.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [u, w] : g[v])
      |              ^

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 312 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 24 ms 340 KB Output is correct
4 Correct 32 ms 336 KB Output is correct
5 Correct 105 ms 316 KB Output is correct
6 Correct 204 ms 416 KB Output is correct
7 Correct 327 ms 420 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 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Execution timed out 1066 ms 320 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 312 KB Output is correct
8 Correct 7 ms 332 KB Output is correct
9 Correct 24 ms 340 KB Output is correct
10 Correct 32 ms 336 KB Output is correct
11 Correct 105 ms 316 KB Output is correct
12 Correct 204 ms 416 KB Output is correct
13 Correct 327 ms 420 KB Output is correct
14 Execution timed out 1066 ms 320 KB Time limit exceeded
15 Halted 0 ms 0 KB -