oj.uz

Submission #1118775

# Submission time Handle Problem Language Result Execution time Memory
1118775 2024-11-26T06:09:50 Z gdragon Toll (BOI17_toll) C++17
100 / 100
 407 ms 364888 KB 
#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 5e4 + 5;
const int M = 1e6 + 5;
const int inf = 1e9 + 7;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
struct DSU {
    int n;
    vector<int> par;
    DSU(int _n = 0) {
        n = _n;
        par.assign(n + 2, -1);
    }
    int root(int v) {
        return par[v] < 0 ? v : (par[v] = root(par[v]));
    }
    bool join(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (par[y] < par[x]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
} dsu;
struct Edge {
    int u, v, c;
    Edge(int _u = 0, int _v = 0, int _c = 0) {
        u = _u; v = _v; c = _c;
    }
} e[M];
vector<ii> adj[N];
int n, K, m, q;
void read() {
    cin >> K >> n >> m >> q;
    dsu = DSU(n);
    for(int i = 1; i <= m; i++) {
        int u, v, c; cin >> u >> v >> c;
        assert(v - u < 2 * K);
        adj[u].push_back({v, c});
        dsu.join(u, v);
        if (K == 1) assert(v == u + 1);
        e[i] = Edge(u, v, c);
    }
}
long long dp[N];
int timer = 0;
long long backtrack(int u, int t) {
    if (u == t) return 0;
    if (u / K >= t / K) return INF;
    long long &res = dp[u];
    if (res != -1) return res;
    res = INF;
    for(auto [v, c]: adj[u]) {
        minimize(res, backtrack(v, t) + c);
    }
    return res;
}
// void solve() {
//     vector<long long> d(n + 2, 0);
//     if (K == 1) {
//         for(int i = 1; i <= m; i++) d[e[i].v] = e[i].c;
//         for(int i = 1; i <= n; i++) d[i] += d[i - 1];
//     }
//     vector<long long> d0(n + 1, INF);
//     d0[0] = 0;
//     priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> heap;
//     heap.push({0, 0});
//     while(!heap.empty()) {
//         auto tmp = heap.top(); heap.pop();
//         long long du = tmp.fi;
//         int u = tmp.se;
//         if (du != d0[u]) continue;
//         for(auto [v, c]: adj[u]) if (minimize(d0[v], du + c)) {
//             heap.push({d0[v], v});
//         }
//     }
//     while(q--) {
//         int u, v; cin >> u >> v;
//         if (u == v) {
//             cout << 0 << endl;
//             continue;
//         }
//         if (u > v || u/K == v/K || dsu.root(u) != dsu.root(v)) {
//             cout << -1 << endl;
//             continue;
//         }
//         if (K == 1) {
//             cout << d[v] - d[u] << endl;
//             continue;
//         }
//         if (u == 0) {
//             cout << (d0[v] == INF ? -1 : d0[v]) << endl;
//             continue;
//         }
//         for(int i = 0; i < n; i++) dp[i] = -1;
//         long long ans = backtrack(u, v);
//         cout << (ans == INF ? -1 : ans) << endl;
//     }
// }
#define LOG 16
long long f[N][LOG + 2][7][7];
void prepare() {
    memset(f, 0x3f, sizeof(f));
    // for(int i = 0; i < n; i++) f[i][0][i % K][i % K] = 0;
    for(int i = 1; i <= m; i++) {
        minimize(f[e[i].u / K][0][e[i].u % K][e[i].v % K], e[i].c);
    }
    int block = n / K + (n % K != 0) - 1;
    for(int j = 1; j <= LOG; j++) {
        for(int i = 0; i + MASK(j) - 1 <= block; i++) {
            for(int r1 = 0; r1 < K; r1++) {
                for(int r2 = 0; r2 < K; r2++) {
                    for(int x = 0; x < K; x++) {
                        if (f[i][j - 1][r1][x] < INF && 
                        f[i + MASK(j - 1)][j - 1][x][r2] < INF) {
                            minimize(f[i][j][r1][r2], f[i][j - 1][r1][x] + f[i + MASK(j - 1)][j - 1][x][r2]);
                        }
                    }
                }
            }
        }
    }
    // cerr << f[0][1][0][2] << endl;
}
long long get(int u, int v) {
    int d = (v / K) - (u / K);
    if (d < 0) return -1;
    vector<vector<long long>> ans(2, vector<long long>(K, INF));
    int bl1 = u / K;
    ans[1][u % K] = 0;
    for(int i = LOG; i >= 0; i--) if (GETBIT(d, i)) {
        swap(ans[0], ans[1]);
        for(int j = 0; j < K; j++) ans[1][j] = INF; 
        for(int r1 = 0; r1 < K; r1++) {
            for(int r2 = 0; r2 < K; r2++) {
                if (f[bl1][i][r1][r2] < INF && ans[0][r1] < INF) {
                    ans[1][r2] = min(ans[1][r2], ans[0][r1] + f[bl1][i][r1][r2]);
                }
            }
        }
        bl1 += MASK(i);
    }
    return (ans[1][v % K] == INF ? -1 : ans[1][v % K]);
}
void solve() {
    prepare();
    while(q--) {
        int u, v; cin >> u >> v;
        cout << get(u, v) << endl;
    }
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   if (fopen(TASK".inp", "r")) {
       freopen(TASK".inp", "r", stdin);
       freopen(TASK".out", "w", stdout);
   }
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

// rmq - rmq2d
// hash
// fw - fw2d
// segtree

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:172:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |        freopen(TASK".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:173:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |        freopen(TASK".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 361360 KB Output is correct
2 Correct 292 ms 358484 KB Output is correct
3 Correct 256 ms 358488 KB Output is correct
4 Correct 279 ms 358408 KB Output is correct
5 Correct 313 ms 358484 KB Output is correct
6 Correct 314 ms 358484 KB Output is correct
7 Correct 323 ms 358532 KB Output is correct
8 Correct 351 ms 361220 KB Output is correct
9 Correct 344 ms 361124 KB Output is correct
10 Correct 341 ms 358736 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 361960 KB Output is correct
2 Correct 335 ms 358656 KB Output is correct
3 Correct 286 ms 358400 KB Output is correct
4 Correct 269 ms 358408 KB Output is correct
5 Correct 259 ms 358476 KB Output is correct
6 Correct 279 ms 358564 KB Output is correct
7 Correct 294 ms 358732 KB Output is correct
8 Correct 273 ms 358732 KB Output is correct
9 Correct 302 ms 361236 KB Output is correct
10 Correct 380 ms 363492 KB Output is correct
11 Correct 355 ms 362244 KB Output is correct
12 Correct 334 ms 361516 KB Output is correct
13 Correct 343 ms 363852 KB Output is correct
14 Correct 348 ms 361684 KB Output is correct
15 Correct 353 ms 361056 KB Output is correct
16 Correct 379 ms 361036 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 358516 KB Output is correct
2 Correct 337 ms 358468 KB Output is correct
3 Correct 289 ms 358488 KB Output is correct
4 Correct 269 ms 358488 KB Output is correct
5 Correct 321 ms 358488 KB Output is correct
6 Correct 260 ms 358572 KB Output is correct
7 Correct 291 ms 358456 KB Output is correct
8 Correct 265 ms 358736 KB Output is correct
9 Correct 264 ms 358564 KB Output is correct
10 Correct 325 ms 361104 KB Output is correct
11 Correct 365 ms 361812 KB Output is correct
12 Correct 397 ms 363376 KB Output is correct
13 Correct 391 ms 363776 KB Output is correct
14 Correct 383 ms 362612 KB Output is correct
15 Correct 327 ms 361020 KB Output is correct
16 Correct 362 ms 361008 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 358516 KB Output is correct
2 Correct 337 ms 358468 KB Output is correct
3 Correct 289 ms 358488 KB Output is correct
4 Correct 269 ms 358488 KB Output is correct
5 Correct 321 ms 358488 KB Output is correct
6 Correct 260 ms 358572 KB Output is correct
7 Correct 291 ms 358456 KB Output is correct
8 Correct 265 ms 358736 KB Output is correct
9 Correct 264 ms 358564 KB Output is correct
10 Correct 325 ms 361104 KB Output is correct
11 Correct 365 ms 361812 KB Output is correct
12 Correct 397 ms 363376 KB Output is correct
13 Correct 391 ms 363776 KB Output is correct
14 Correct 383 ms 362612 KB Output is correct
15 Correct 327 ms 361020 KB Output is correct
16 Correct 362 ms 361008 KB Output is correct
17 Correct 398 ms 361776 KB Output is correct
18 Correct 296 ms 358488 KB Output is correct
19 Correct 294 ms 358388 KB Output is correct
20 Correct 295 ms 358476 KB Output is correct
21 Correct 300 ms 358620 KB Output is correct
22 Correct 263 ms 358576 KB Output is correct
23 Correct 288 ms 358572 KB Output is correct
24 Correct 304 ms 358808 KB Output is correct
25 Correct 303 ms 358644 KB Output is correct
26 Correct 312 ms 358640 KB Output is correct
27 Correct 317 ms 360996 KB Output is correct
28 Correct 384 ms 363432 KB Output is correct
29 Correct 322 ms 364024 KB Output is correct
30 Correct 339 ms 362648 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 361360 KB Output is correct
2 Correct 292 ms 358484 KB Output is correct
3 Correct 256 ms 358488 KB Output is correct
4 Correct 279 ms 358408 KB Output is correct
5 Correct 313 ms 358484 KB Output is correct
6 Correct 314 ms 358484 KB Output is correct
7 Correct 323 ms 358532 KB Output is correct
8 Correct 351 ms 361220 KB Output is correct
9 Correct 344 ms 361124 KB Output is correct
10 Correct 341 ms 358736 KB Output is correct
11 Correct 407 ms 361960 KB Output is correct
12 Correct 335 ms 358656 KB Output is correct
13 Correct 286 ms 358400 KB Output is correct
14 Correct 269 ms 358408 KB Output is correct
15 Correct 259 ms 358476 KB Output is correct
16 Correct 279 ms 358564 KB Output is correct
17 Correct 294 ms 358732 KB Output is correct
18 Correct 273 ms 358732 KB Output is correct
19 Correct 302 ms 361236 KB Output is correct
20 Correct 380 ms 363492 KB Output is correct
21 Correct 355 ms 362244 KB Output is correct
22 Correct 334 ms 361516 KB Output is correct
23 Correct 343 ms 363852 KB Output is correct
24 Correct 348 ms 361684 KB Output is correct
25 Correct 353 ms 361056 KB Output is correct
26 Correct 379 ms 361036 KB Output is correct
27 Correct 297 ms 358516 KB Output is correct
28 Correct 337 ms 358468 KB Output is correct
29 Correct 289 ms 358488 KB Output is correct
30 Correct 269 ms 358488 KB Output is correct
31 Correct 321 ms 358488 KB Output is correct
32 Correct 260 ms 358572 KB Output is correct
33 Correct 291 ms 358456 KB Output is correct
34 Correct 265 ms 358736 KB Output is correct
35 Correct 264 ms 358564 KB Output is correct
36 Correct 325 ms 361104 KB Output is correct
37 Correct 365 ms 361812 KB Output is correct
38 Correct 397 ms 363376 KB Output is correct
39 Correct 391 ms 363776 KB Output is correct
40 Correct 383 ms 362612 KB Output is correct
41 Correct 327 ms 361020 KB Output is correct
42 Correct 362 ms 361008 KB Output is correct
43 Correct 398 ms 361776 KB Output is correct
44 Correct 296 ms 358488 KB Output is correct
45 Correct 294 ms 358388 KB Output is correct
46 Correct 295 ms 358476 KB Output is correct
47 Correct 300 ms 358620 KB Output is correct
48 Correct 263 ms 358576 KB Output is correct
49 Correct 288 ms 358572 KB Output is correct
50 Correct 304 ms 358808 KB Output is correct
51 Correct 303 ms 358644 KB Output is correct
52 Correct 312 ms 358640 KB Output is correct
53 Correct 317 ms 360996 KB Output is correct
54 Correct 384 ms 363432 KB Output is correct
55 Correct 322 ms 364024 KB Output is correct
56 Correct 339 ms 362648 KB Output is correct
57 Correct 400 ms 364888 KB Output is correct
58 Correct 356 ms 361088 KB Output is correct
59 Correct 328 ms 362144 KB Output is correct