Submission #879561

#	Time	Username	Problem	Language	Result	Execution time	Memory
879561		Shayan86	Toll (APIO13_toll)	C++17	0 / 100	20 ms	42588 KiB

toll

#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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22