oj.uz

Submission #533475

# Submission time Handle Problem Language Result Execution time Memory
533475 2022-03-06T06:32:04 Z N1NT3NDO Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 9228 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;
bool used[N];
ll dst[N][N][N];


/*
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);
    }
}
*/

void calc(int x)
{
    for(int i = 1; i <= n; i++)
      for(int j = 0; j <= k; j++)
        dst[x][i][j] = 1e18;
    dst[x][x][0] = 0;
    set< pair<ll, pair<int, int> > > se;


    se.insert({0, {0, x}});

    while(sz(se) > 0)
    {
        auto c = *se.begin(); se.erase(se.begin());
        ll d = c.fi;
        int v = c.sd.sd, skok = c.sd.fi;

        if (dst[x][v][skok] < d) continue;

        for(auto [u, w] : g[v])
        {
            if (skok + 1 <= k && dst[x][v][skok] + w < dst[x][u][skok + 1])
            {
                dst[x][u][skok + 1] = dst[x][v][skok] + w;
                se.insert({dst[x][u][skok + 1], {skok + 1, u}});
            }
        }
    }

}

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;

    k = min(k, n);

    for(int i = 1; i <= n; i++)
      calc(i);

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

        for(int i = 0; i <= k; i++) ans = min(ans, dst[S][F][i]);

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

}

Compilation message

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

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 4 ms 3404 KB Output is correct
3 Correct 4 ms 3452 KB Output is correct
4 Correct 4 ms 3404 KB Output is correct
5 Correct 7 ms 3404 KB Output is correct
6 Correct 9 ms 3508 KB Output is correct
7 Correct 11 ms 3460 KB Output is correct

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 Correct 38 ms 3480 KB Output is correct
8 Correct 124 ms 3696 KB Output is correct
9 Correct 8 ms 3404 KB Output is correct
10 Correct 85 ms 3412 KB Output is correct
11 Correct 43 ms 3584 KB Output is correct
12 Correct 214 ms 3908 KB Output is correct
13 Correct 347 ms 8956 KB Output is correct
14 Correct 518 ms 9228 KB Output is correct
15 Execution timed out 1088 ms 7836 KB Time limit exceeded
16 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 3 ms 3404 KB Output is correct
8 Correct 4 ms 3404 KB Output is correct
9 Correct 4 ms 3452 KB Output is correct
10 Correct 4 ms 3404 KB Output is correct
11 Correct 7 ms 3404 KB Output is correct
12 Correct 9 ms 3508 KB Output is correct
13 Correct 11 ms 3460 KB Output is correct
14 Correct 38 ms 3480 KB Output is correct
15 Correct 124 ms 3696 KB Output is correct
16 Correct 8 ms 3404 KB Output is correct
17 Correct 85 ms 3412 KB Output is correct
18 Correct 43 ms 3584 KB Output is correct
19 Correct 214 ms 3908 KB Output is correct
20 Correct 347 ms 8956 KB Output is correct
21 Correct 518 ms 9228 KB Output is correct
22 Execution timed out 1088 ms 7836 KB Time limit exceeded
23 Halted 0 ms 0 KB -