oj.uz

Submission #879561

# Submission time Handle Problem Language Result Execution time Memory
879561 2023-11-27T16:22:07 Z Shayan86 Toll (APIO13_toll) C++17
0 / 100
 20 ms 42588 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

#define lid (id*2)
#define rid (id*2+1)
#define mid ((l+r)/2)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll K = 5;
const ll N = 5e4 + 50;
const ll inf = 1e9;

ll n, m, k, q, cnt;

vector<pii> adj[N];

struct dt{
    int dist[K][K];
    dt(int x = inf, int y = K){
        for(int i = 0; i < y; i++){
            for(int j = 0; j < y; j++){
                dist[i][j] = inf;
            }
        }
    }
};

dt merg(dt l, dt r){
    dt out;
    for(int i = 0; i < k; i++){
        for(int j = 0; j < k; j++){
            for(int o = 0; o < k; o++){
                out.dist[i][j] = min(out.dist[i][j], l.dist[i][o] + r.dist[o][j]);
            }
        }
    }
    return out;
}

dt seg[N*4];

void build(int l = 0, int r = cnt, int id = 1){
    if(l+1 == r){
        for(int i = l*k; i < l*k+k; i++){
            for(auto [j, w]: adj[i]){
                seg[id].dist[i%k][j%k] = min(seg[id].dist[i%k][j%k], w);
            }
        }
        return;
    }

    build(l, mid, lid);
    build(mid, r, rid);
    seg[id] = merg(seg[lid], seg[rid]);
}

dt get(int ql, int qr, int l = 0, int r = cnt, int id = 1){
    if(ql <= l && r <= qr) return seg[id];
    if(qr <= mid) return get(ql, qr, l, mid, lid);
    if(mid <= ql) return get(ql, qr, mid, r, rid);
    return merg(get(ql, qr, l, mid, lid), get(ql, qr, mid, r, rid));
}


int main(){
    fast_io;

    cin >> k >> n >> m >> q;

    while(n % k != 0) n++;
    cnt = n/k;

    int u, v, w;
    for(int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        adj[u].pb(Mp(v, w));
    }

    build();

    while(q--){
        cin >> u >> v;

        if(u/k == v/k){
            cout << -1 << endl;
            continue;
        }

        ll out = get(u/k, v/k).dist[u%k][v%k];
        if(out < inf) cout << out << endl;
        else cout << -1 << endl;
    }

}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 42588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 42588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 42588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 42588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 42588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -