oj.uz

Submission #628072

# Submission time Handle Problem Language Result Execution time Memory
628072 2022-08-13T04:37:52 Z nttt Toll (BOI17_toll) C++14
18 / 100
 3000 ms 6588 KB 
#include<bits/stdc++.h>
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 pii pair<ll, int>
#define all(x) (x).begin(), (x).end()
#define task "name"

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 5e4 + 3;
const int M = 1e4 + 9;
const int BASE = 10;

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;}

struct query
{
    int u, v, id;
    bool operator < (const query &a) const
    {
        return u < a.u;
    }
} que[M];
int k, n, m, q;
vector<pii> adj[N];
ll d[N];
ll ans[M];
void dijkstra(int s)
{
    memset(d, 0x3f, sizeof d);
    priority_queue<pii, vector<pii>, greater<pii>> kew;
    kew.push(mp(0, s));
    d[s] = 0;

    while(!kew.empty())
    {
        int u = kew.top().se;
        ll du = kew.top().fi;
        kew.pop();
        for(pii i : adj[u])
        {
            int v = i.se;
            ll uv = i.fi;
            if(minimize(d[v], du + uv))
            {
                kew.push(mp(d[v], v));
            }
        }
    }
}
void Solve()
{
    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));
    }
    for(int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;
        que[i] = {u, v, i};
    }
    sort(que + 1, que + 1 + q);
    int s = -1;
    for(int i = 1; i <= q; i++)
    {
        if(que[i].u != s)
        {
            s = que[i].u;
            dijkstra(s);
        }
        ans[que[i].id] = d[que[i].v];
    }
    for(int i = 1; i <= q; i++)
    {
        if(ans[i] < loo) cout << ans[i] << '\n';
        else cout << -1 << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    int T = 1;
    //cin >> T;
    while(T--)
    {
        Solve();
    }

    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4648 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 3 ms 2152 KB Output is correct
8 Correct 4 ms 2132 KB Output is correct
9 Correct 18 ms 3604 KB Output is correct
10 Correct 46 ms 6056 KB Output is correct
11 Correct 50 ms 4752 KB Output is correct
12 Correct 24 ms 4044 KB Output is correct
13 Correct 55 ms 6588 KB Output is correct
14 Correct 31 ms 4544 KB Output is correct
15 Correct 28 ms 3956 KB Output is correct
16 Correct 29 ms 3884 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 4 ms 1876 KB Output is correct
8 Correct 10 ms 2068 KB Output is correct
9 Correct 8 ms 1876 KB Output is correct
10 Correct 19 ms 3460 KB Output is correct
11 Correct 207 ms 4396 KB Output is correct
12 Correct 331 ms 5836 KB Output is correct
13 Correct 362 ms 6256 KB Output is correct
14 Correct 328 ms 5096 KB Output is correct
15 Correct 210 ms 3896 KB Output is correct
16 Correct 189 ms 3880 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 4 ms 1876 KB Output is correct
8 Correct 10 ms 2068 KB Output is correct
9 Correct 8 ms 1876 KB Output is correct
10 Correct 19 ms 3460 KB Output is correct
11 Correct 207 ms 4396 KB Output is correct
12 Correct 331 ms 5836 KB Output is correct
13 Correct 362 ms 6256 KB Output is correct
14 Correct 328 ms 5096 KB Output is correct
15 Correct 210 ms 3896 KB Output is correct
16 Correct 189 ms 3880 KB Output is correct
17 Execution timed out 3069 ms 4368 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 3070 ms 3612 KB Time limit exceeded
2 Halted 0 ms 0 KB -