oj.uz

Submission #629590

# Submission time Handle Problem Language Result Execution time Memory
629590 2022-08-14T17:13:49 Z Duy_e Toll (BOI17_toll) C++14
7 / 100
 457 ms 14668 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 5e4 + 5;
const long long block = 200;

#define data array<array<ll, 5>, 5>

int n, m, k, q, id[N];

vector <pii> d[N];

struct seg {
    data f;
    int l, r;

    void set(ll val) {
        for (int u = 0; u < 5; u ++) for (int v = 0; v < 5; v ++) f[u][v] = val;
    }  

    void init(int i) {
        set(INF);
        for (int j = 0; j < 5; j ++) f[j][j] = 0;
        l = r = i;
    }

};

seg combine(seg a, seg b) {
    seg ans;
    ans.l = a.l; ans.r = b.r;
    ans.set(INF);
    for (int u = 0; u < k; u ++) for (int v = 0; v < k; v ++) {
        int cur = a.r * k + v;
        for (pii nxt: d[cur]) {
            ll w = nxt.nd, node = nxt.st % k;
            for (int x = 0; x < k; x ++) {
                ans.f[u][x] = min(ans.f[u][x], a.f[u][v] + b.f[node][x] + w);
            }
        }
    }

    return ans;
}

seg sec[N], ind[N];
int L[N], R[N];

ll query(int u, int v) {
    int l = u / k, r = v / k;
    if (l >= r) return 0;

    seg ans = ind[l];


    int idL = l / block, idR = r / block;
    if (idL == idR) {
        for (int i = l + 1; i <= r; i ++)
            ans = combine(ans, ind[i]);

        return ans.f[u % k][v % k];
    }

    for (int i = l + 1; i <= R[idL]; i ++) 
        ans = combine(ans, ind[i]);
    for (int i = idL + 1; i < idR; i ++)
        ans = combine(ans, sec[i]);
    for (int i = L[idR]; i <= r; i ++)
        ans = combine(ans, ind[i]);
    
    return ans.f[u % k][v % k];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    // #endif
    
    cin >> k >> n >> m >> q;

    for (int i = 1, u, v, t; i <= m; i ++) {
        cin >> u >> v >> t;
        d[u].push_back({v, t});
    }

    memset(L, -1, sizeof L);
    memset(R, -1, sizeof R);

    for (int i = 0; i <= n / k; i ++) {
        ind[i].init(i);
        R[i / block] = i;
        if (L[i / block] == -1) L[i / block] = i;
    }

    int m = n / k;
    for (int i = 0; i <= m / block; i ++) 
        sec[i] = ind[L[i]];
    
    for (int i = 0; i <= m; i ++) {
        if (i != L[i / block]) 
            sec[i / block] = combine(sec[i / block], ind[i]);
    }

    int u, v;

    auto fix = [&] (ll x) {
        if (x >= 1e15) return -1ll;
        return x;
    };
 
    while (q --) {
        cin >> u >> v;
        cout << fix(query(u, v)) << '\n';
    }

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮
**/

Compilation message

toll.cpp:125:9: warning: "/*" within comment [-Wcomment]
  125 | /**  /\_/\
      |

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 14668 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1892 KB Output is correct
5 Correct 12 ms 2160 KB Output is correct
6 Correct 16 ms 2160 KB Output is correct
7 Correct 12 ms 2156 KB Output is correct
8 Correct 274 ms 14604 KB Output is correct
9 Correct 252 ms 14500 KB Output is correct
10 Correct 130 ms 12236 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 11276 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Incorrect 2 ms 1888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 14668 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1892 KB Output is correct
5 Correct 12 ms 2160 KB Output is correct
6 Correct 16 ms 2160 KB Output is correct
7 Correct 12 ms 2156 KB Output is correct
8 Correct 274 ms 14604 KB Output is correct
9 Correct 252 ms 14500 KB Output is correct
10 Correct 130 ms 12236 KB Output is correct
11 Correct 457 ms 11276 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Incorrect 2 ms 1888 KB Output isn't correct
14 Halted 0 ms 0 KB -