oj.uz

Submission #694112

# Submission time Handle Problem Language Result Execution time Memory
694112 2023-02-03T20:32:20 Z CDuong Toll (BOI17_toll) C++17
7 / 100
 346 ms 160032 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname "disrupt"
#define all(x) x.begin(), x.end()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
using namespace std;

const int mxN = 5e4 + 5;
const int mod = 1e9 + 7;
const int lim = 16;
const ll oo = 1e18;

struct matrix {
    ll a[5][5];

    matrix() {memset(a, 0x3f, sizeof a);}

    matrix operator + (const matrix &o) {
        matrix res;
        for(int i = 0; i < 5; ++i)
            for(int j = 0; j < 5; ++j)
                for(int k = 0; k < 5; ++k) {
                    if(a[i][j] > oo || o.a[j][k] > oo)
                        continue;
                    res.a[i][k] = min(res.a[i][k], a[i][j] + o.a[j][k]);
                }
        return res;
    }
};

int n, m, k, q;
int par[mxN][lim];
matrix path[mxN][lim];

void solve() {
    cin >> k >> n >> m >> q;
    for(int i = 0; i < n; ++i)
        par[i][0] = i + 1;
    par[n][0] = n;
    for(int i = 1; i <= m; ++i) {
        int u, v, t;
        cin >> u >> v >> t;
        path[u / k][0].a[u % k][v % k] = t;
    }
    for(int i = 1; i < lim; ++i) {
        for(int j = 0; j * k <= n; ++j) {
            par[j][i] = par[par[j][i - 1]][i - 1];
            path[j][i] = path[j][i - 1] + path[par[j][i - 1]][i - 1];
        }
    }
    while(q--) {
        int a, b;
        cin >> a >> b;
        if(b < a) {
            cout << "-1\n";
            continue;
        }
        if(a == b) {
            cout << "0\n";
            continue;
        }
        matrix res;
        for(int i = 0; i < 5; ++i)
            for(int j = 0; j < 5; ++j)
                res.a[i][j] = 0;
        int floor_a = a / k, floor_b = b / k;
        for(int i = lim - 1; i >= 0; --i) {
            int en = floor_a + (1 << i);
            if(en <= floor_b) {
                res = res + path[floor_a][i];
                floor_a = par[floor_a][i];
            }
        }
        ll ans = res.a[a % k][b % k];
        if(ans > oo)
            ans = -1;
        cout << ans << "\n";
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".in", "r"))
        assert(freopen(taskname".in", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
    auto end = chrono::high_resolution_clock::now();
    cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
    cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 160004 KB Output is correct
2 Correct 59 ms 156832 KB Output is correct
3 Correct 60 ms 156760 KB Output is correct
4 Correct 71 ms 156876 KB Output is correct
5 Correct 64 ms 156912 KB Output is correct
6 Correct 65 ms 156832 KB Output is correct
7 Correct 64 ms 156832 KB Output is correct
8 Correct 338 ms 160028 KB Output is correct
9 Correct 346 ms 160016 KB Output is correct
10 Correct 327 ms 160000 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 160004 KB Output is correct
2 Correct 59 ms 156832 KB Output is correct
3 Correct 60 ms 156760 KB Output is correct
4 Correct 71 ms 156876 KB Output is correct
5 Correct 64 ms 156912 KB Output is correct
6 Correct 65 ms 156832 KB Output is correct
7 Correct 64 ms 156832 KB Output is correct
8 Correct 338 ms 160028 KB Output is correct
9 Correct 346 ms 160016 KB Output is correct
10 Correct 327 ms 160000 KB Output is correct
11 Incorrect 228 ms 160032 KB Output isn't correct
12 Halted 0 ms 0 KB -