oj.uz

Submission #1039224

# Submission time Handle Problem Language Result Execution time Memory
1039224 2024-07-30T14:49:43 Z n3rm1n Toll (BOI17_toll) C++17
0 / 100
 27 ms 9436 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;
long long is[MAXN];
long long pref[MAXN], cnt[MAXN];
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;
        is[x] = c;
        g[x].push_back(make_pair(y, c));
    }
    for (int i = 0; i < n; ++ i)
    {
        if(i)pref[i] = pref[i-1];
        pref[i] += is[i];
        if(i)cnt[i] = cnt[i-1];
        if(is[i])cnt[i] ++;
    }
}

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;

        if(k == 1)
        {
            int diff = to - from;
            if(from > to)
            {
                cout << -1 << endl;
                continue;
            }
            int cnttt = cnt[to-1] - cnt[from];
            int summ = pref[to-1];
            if(from)summ-= pref[from-1];
            if(cnttt == diff)cout << summ << endl;
            else cout << -1 << endl;
        }
        que[from].push_back({to, i});
        isstart[from] = 1;
    }

    if(k == 1)exit(0);
    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:50:21: warning: variable 'wdist' set but not used [-Wunused-but-set-variable]
   50 |     long long wver, wdist;
      |                     ^~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 7000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9436 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 4 ms 3164 KB Output is correct
7 Incorrect 3 ms 3164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 7000 KB Output isn't correct
2 Halted 0 ms 0 KB -