oj.uz

Submission #445909

# Submission time Handle Problem Language Result Execution time Memory
445909 2021-07-20T07:25:21 Z prvocislo Toll (BOI17_toll) C++17
8 / 100
 3000 ms 5648 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int infy = 1e9 + 5;
vector<int> solve(int k, int n, int m, int q, const vector<vector<int> > &g, const vector<pair<int, int> > &v) // riesenie O(q*n^2)
{
    vector<int> ans(q);
    for (int i = 0; i < q; i++)
    {
        int a = v[i].first, b = v[i].second;
        set<pair<int, int> > pq;
        vector<int> dist(n, infy);
        pq.insert({0, a});
        while (!pq.empty())
        {
            int d = pq.begin()->first, u = pq.begin()->second;
            pq.erase(pq.begin());
            if (dist[u] != infy) continue;
            dist[u] = d;
            for (int j = 0; j < k; j++)
            {
                int v = (u/k+1)*k + j;
                if (g[u][j] == infy || dist[v] != infy) continue;
                pq.insert({d+g[u][j], v});
            }
        }
        ans[i] = dist[b] == infy ? -1 : dist[b];
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    while (t--)
    {
        int k, n, m, q;
        cin >> k >> n >> m >> q;
        vector<vector<int> > g(n, vector<int> (k, infy));
        for (int i = 0, a, b, d; i < m; i++)
        {
            cin >> a >> b >> d;
            g[a][b%k] = d;
        }
        vector<pair<int, int> > v(q);
        for (int i = 0; i < q; i++) cin >> v[i].first >> v[i].second;
        vector<int> ans = solve(k, n, m, q, g, v);
        for (int i : ans) cout << i << "\n";
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 4228 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 3077 ms 4936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.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 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 11 ms 404 KB Output is correct
8 Correct 34 ms 412 KB Output is correct
9 Correct 25 ms 332 KB Output is correct
10 Correct 30 ms 4044 KB Output is correct
11 Correct 607 ms 4784 KB Output is correct
12 Correct 928 ms 5392 KB Output is correct
13 Correct 1111 ms 5648 KB Output is correct
14 Correct 832 ms 5020 KB Output is correct
15 Correct 654 ms 3224 KB Output is correct
16 Correct 576 ms 3148 KB Output is correct

Subtask #4
0 / 31.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 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 11 ms 404 KB Output is correct
8 Correct 34 ms 412 KB Output is correct
9 Correct 25 ms 332 KB Output is correct
10 Correct 30 ms 4044 KB Output is correct
11 Correct 607 ms 4784 KB Output is correct
12 Correct 928 ms 5392 KB Output is correct
13 Correct 1111 ms 5648 KB Output is correct
14 Correct 832 ms 5020 KB Output is correct
15 Correct 654 ms 3224 KB Output is correct
16 Correct 576 ms 3148 KB Output is correct
17 Execution timed out 3074 ms 4828 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 3083 ms 4228 KB Time limit exceeded
2 Halted 0 ms 0 KB -