oj.uz

Submission #1083158

# Submission time Handle Problem Language Result Execution time Memory
1083158 2024-09-02T17:00:51 Z _8_8_ Toll (BOI17_toll) C++17
17 / 100
 255 ms 28620 KB 
#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 5e4 + 12, MOD = (int)1e9 + 7;

int k, n, m, q, b;
vector<pair<int,int>> g[N], o;
vector<ll> di[N];
const int inf = 1e9 + 1;
vector<ll> tr(vector<ll> prev,int l, int r) {
    vector<ll> ret(k,inf);
    assert(l % k == 0);
    for(int i = l; i <= r; i++) {
        int f = i % k;
        for(auto [to,w]:g[i]) {
            ret[to % k] = min(ret[to % k],prev[f] + w);
        }
    }
    return ret;
}
void prec() {
    for(int i = (int)o.size() - 1; i >= 0; i--) {
        if(i % b == 0) {
            int nx = i + b;
            int l = o[i].first, r = o[i].second;
            for(int j = l; j <= r; j++) {
                vector<ll> dd(k,inf);
                dd[j%k] = 0;
                // cout << j << '\n';
                for(int _i = i + 1; _i < (int)o.size(); _i++) {
                    vector<ll> nv = tr(dd,o[_i - 1].first,o[_i - 1].second);
                    for(auto f:nv) {    
                        di[j].push_back(f);
                        // cout << f << ' ';
                    }
                    dd = nv;
                }
                // cout << "_____________\n";
            }
        }
    }
}
void test() {
    cin >> k >> n >> m >> q;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b,c});
    }
    for(int i = 0; i <= n; i++) {
        int l = i * k, r = (i + 1) * k - 1;
        if(l >= n) break;
        if(r >= n) {
                r = n - 1;
        }
        o.push_back({l,r});
    }
    for(int i = 0; i < n; i++) {
        sort(g[i].begin(),g[i].end());
        vector<pair<int,int>> nv;
        for(auto [x,y]:g[i]) {
            if(nv.empty() || nv.back().first != x) {
                nv.emplace_back(x,y);
            }
        }
        g[i].swap(nv);
        assert((int)g[i].size() <= k);
    }
    b = 500;
    // b = 1;
    prec();
    // return;
    while(q--) {
        int a, r;
        cin >> a >> r;
        if(a / k >= r / k) {
            cout << -1 << '\n';
            continue;
        }
        int x = a / k, y = r / k;
        vector<ll> cur(k,inf);
        cur[a%k] = 0;
        while(x % b != 0) {
            x++;
            cur = tr(cur,o[x - 1].first,o[x - 1].second);
            if(x == y) {
                break;
            }
        }
        ll res = inf;
        if(x == y) {
            res = cur[y % k];
        } else {
            for(int i = 0; i < k; i++) {
                int nx = (x + 1) * k;
                res = min(res,di[o[x].first + i][r - nx] + cur[i]);
            }
        }
        if(res == inf) res = -1;
        cout << res << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1; 
    // cin >> t;
    while(t--) 
        test();

    return 0;
}

Compilation message

toll.cpp: In function 'void prec()':
toll.cpp:26:17: warning: unused variable 'nx' [-Wunused-variable]
   26 |             int nx = i + b;
      |                 ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 25296 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 9 ms 2652 KB Output is correct
6 Correct 7 ms 2888 KB Output is correct
7 Correct 7 ms 2888 KB Output is correct
8 Correct 238 ms 26264 KB Output is correct
9 Correct 249 ms 26068 KB Output is correct
10 Correct 197 ms 23760 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 26712 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 140 ms 26312 KB Output is correct
10 Correct 108 ms 28620 KB Output is correct
11 Correct 132 ms 26616 KB Output is correct
12 Correct 98 ms 26256 KB Output is correct
13 Correct 65 ms 16080 KB Output is correct
14 Correct 51 ms 13772 KB Output is correct
15 Correct 42 ms 13264 KB Output is correct
16 Correct 41 ms 13272 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 25296 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 9 ms 2652 KB Output is correct
6 Correct 7 ms 2888 KB Output is correct
7 Correct 7 ms 2888 KB Output is correct
8 Correct 238 ms 26264 KB Output is correct
9 Correct 249 ms 26068 KB Output is correct
10 Correct 197 ms 23760 KB Output is correct
11 Correct 137 ms 26712 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 3 ms 2908 KB Output is correct
18 Correct 3 ms 2908 KB Output is correct
19 Correct 140 ms 26312 KB Output is correct
20 Correct 108 ms 28620 KB Output is correct
21 Correct 132 ms 26616 KB Output is correct
22 Correct 98 ms 26256 KB Output is correct
23 Correct 65 ms 16080 KB Output is correct
24 Correct 51 ms 13772 KB Output is correct
25 Correct 42 ms 13264 KB Output is correct
26 Correct 41 ms 13272 KB Output is correct
27 Correct 1 ms 2652 KB Output is correct
28 Incorrect 1 ms 2652 KB Output isn't correct
29 Halted 0 ms 0 KB -