oj.uz

Submission #1039189

# Submission time Handle Problem Language Result Execution time Memory
1039189 2024-07-30T14:20:25 Z n3rm1n Toll (BOI17_toll) C++17
18 / 100
 3000 ms 10836 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 5e4 + 10, MAXM = 1e4 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long k, n, m, q;
vector < pair < long long, long long > > g[MAXN];
void read()
{
    cin >> k >> n >> m >> q;
    for (long long i = 1; i <= m; ++ i)
    {
        long long x, y, c;
        cin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }
}

long long isstart[MAXN];
vector < pair < long long, long long > > que[MAXN];
long long st, dist[MAXN], inf = 1e17; /// fix
long long visited[MAXN];
void dijkstra()
{
    for (long long i = 0; i < n; ++ i)
    {
        dist[i] = inf;
        visited[i] = 0;
    }
    dist[st] = 0;

    priority_queue < pair < long long, long long > > q;
    q.push({0, st});

    long long wver, wdist;
    while(q.size())
    {
        wdist = -q.top().first;
        wver = q.top().second;
        q.pop();
        if(visited[wver])continue;
        visited[wver] = 1;
        for (auto nb: g[wver])
        {
            if(dist[nb.first] > dist[wver] + nb.second)
            {
                dist[nb.first] = dist[wver] + nb.second;
                q.push(make_pair(-dist[nb.first], nb.first));
            }
        }
    }


}
long long ans[MAXN];
void precompute()
{
    for (long long i = 1; i <= q; ++ i)
    {
        long long from, to;
        cin >> from >> to;
        que[from].push_back({to, i});
        isstart[from] = 1;
    }

    memset(ans, -1, sizeof(ans));
    for (long long i = 0; i < n; ++ i)
    {
        if(!isstart[i])continue;
       // cout << i << endl;

        st = i;
        dijkstra();

        for (auto to: que[i])
        {
           // cout << "to " << to.first << " " << dist[to.first] << endl;
            if(dist[to.first] != inf)ans[to.second] = dist[to.first];
        }
    }
    for (long long i = 1; i <= q; ++ i)
        cout << ans[i] << endl;
}
int main()
{
    speed();

    read();
    precompute();
    return 0;
}

Compilation message

toll.cpp: In function 'void dijkstra()':
toll.cpp:40:21: warning: variable 'wdist' set but not used [-Wunused-but-set-variable]
   40 |     long long wver, wdist;
      |                     ^~~~~

Subtask #1
0 / 7.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8412 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 3 ms 4324 KB Output is correct
8 Correct 3 ms 4312 KB Output is correct
9 Correct 14 ms 6568 KB Output is correct
10 Correct 38 ms 10436 KB Output is correct
11 Correct 28 ms 8492 KB Output is correct
12 Correct 19 ms 7640 KB Output is correct
13 Correct 39 ms 10836 KB Output is correct
14 Correct 30 ms 8044 KB Output is correct
15 Correct 20 ms 7256 KB Output is correct
16 Correct 21 ms 6904 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 4036 KB Output is correct
7 Correct 3 ms 3932 KB Output is correct
8 Correct 8 ms 4188 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 19 ms 6500 KB Output is correct
11 Correct 167 ms 7988 KB Output is correct
12 Correct 267 ms 10256 KB Output is correct
13 Correct 285 ms 10832 KB Output is correct
14 Correct 246 ms 9052 KB Output is correct
15 Correct 172 ms 7256 KB Output is correct
16 Correct 177 ms 7260 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 4036 KB Output is correct
7 Correct 3 ms 3932 KB Output is correct
8 Correct 8 ms 4188 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 19 ms 6500 KB Output is correct
11 Correct 167 ms 7988 KB Output is correct
12 Correct 267 ms 10256 KB Output is correct
13 Correct 285 ms 10832 KB Output is correct
14 Correct 246 ms 9052 KB Output is correct
15 Correct 172 ms 7256 KB Output is correct
16 Correct 177 ms 7260 KB Output is correct
17 Execution timed out 3032 ms 8280 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 3055 ms 7004 KB Time limit exceeded
2 Halted 0 ms 0 KB -