oj.uz

Submission #628071

# Submission time Handle Problem Language Result Execution time Memory
628071 2022-08-13T04:37:37 Z nttt Toll (BOI17_toll) C++14
18 / 100
 3000 ms 6688 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;
        if(u > v) swap(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 3061 ms 3572 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 4616 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 1 ms 1876 KB Output is correct
7 Correct 4 ms 2132 KB Output is correct
8 Correct 4 ms 2200 KB Output is correct
9 Correct 19 ms 3676 KB Output is correct
10 Correct 57 ms 5996 KB Output is correct
11 Correct 35 ms 4712 KB Output is correct
12 Correct 25 ms 4156 KB Output is correct
13 Correct 49 ms 6688 KB Output is correct
14 Correct 31 ms 4488 KB Output is correct
15 Correct 27 ms 3924 KB Output is correct
16 Correct 28 ms 3964 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 1876 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 5 ms 1876 KB Output is correct
8 Correct 11 ms 2072 KB Output is correct
9 Correct 9 ms 1876 KB Output is correct
10 Correct 19 ms 3448 KB Output is correct
11 Correct 203 ms 4404 KB Output is correct
12 Correct 318 ms 5836 KB Output is correct
13 Correct 388 ms 6252 KB Output is correct
14 Correct 323 ms 5096 KB Output is correct
15 Correct 202 ms 3796 KB Output is correct
16 Correct 214 ms 3884 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 1876 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 5 ms 1876 KB Output is correct
8 Correct 11 ms 2072 KB Output is correct
9 Correct 9 ms 1876 KB Output is correct
10 Correct 19 ms 3448 KB Output is correct
11 Correct 203 ms 4404 KB Output is correct
12 Correct 318 ms 5836 KB Output is correct
13 Correct 388 ms 6252 KB Output is correct
14 Correct 323 ms 5096 KB Output is correct
15 Correct 202 ms 3796 KB Output is correct
16 Correct 214 ms 3884 KB Output is correct
17 Execution timed out 3079 ms 4452 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 3061 ms 3572 KB Time limit exceeded
2 Halted 0 ms 0 KB -