Submission #392786

#	Time	Username	Problem	Language	Result	Execution time	Memory
392786		Victor	Toll (BOI17_toll)	C++17	56 / 100	3068 ms	7736 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

int main() {
    vii graph[50001];
    int n, memo[50001], k, m, o;
    scanf("%d %d %d %d", &k, &n, &m, &o);

    rep(i, 0, m) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        graph[u].emplace_back(v, w);
    }

    int ans[10000];
    iii orders[10000];

    rep(i, 0, o) {
        orders[i].second.second = i;
        scanf("%d %d", &orders[i].first, &orders[i].second.first);
        orders[i].second.first *= -1;
    }

    sort(orders, orders + o);

    rep(l, 0, o) {
        int a = orders[l].first, b = -orders[l].second.first;

        if (!l || a != orders[l - 1].first) {
            fill(memo + a, memo + b + 1, INF);
            memo[a] = 0;
            rep(i, a, b) {
                if (INF == memo[i]) continue;
                trav(j, graph[i]) {
                    int v, w;
                    tie(v, w) = j;
                    memo[v] = min(memo[v], memo[i] + w);
                }
            }
        }
        ans[orders[l].second.second] = memo[b] == INF ? -1 : memo[b];
    }
    rep(i,0,o)printf("%d\n",ans[i]);
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     scanf("%d %d %d %d", &k, &n, &m, &o);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |         scanf("%d %d %d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d %d", &orders[i].first, &orders[i].second.first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 0 / 44