제출 #479841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479841		MohammadAghil	Toll (BOI17_toll)	C++14	100 / 100	89 ms	11776 KiB

toll

#include <bits/stdc++.h> 
using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
const ll mod = 998244353, maxn = 5e4 + 5, maxk = 5, maxlg = 18, inf = 1e9 + 5;

struct Query{
    pp a, b;
    int id;
};

int grp[maxn][maxk][maxk], ans[maxn], val[maxn][maxk][maxk], k;


void slv(int lx, int rx, vector<Query> v){
    if(lx >= rx || v.empty()){
        for(auto c: v){
            ans[c.id] = -1;
        }
        return;
    }
    // cout << lx << ' ' << rx << ": ";
    // for(auto c: v) cout << c.id << ' '; cout << endl;

    int mid = (lx + rx) >> 1;
    rep(i,0,k){
        rep(j,0,k){
            if(i != j) val[mid][i][j] = inf;
            else val[mid][i][j] = 0;
        }
    }
    per(i,mid - 1, lx){
        rep(f,0,k){
            rep(e,0,k){
                val[i][f][e] = inf;
                rep(x,0,k){
                    val[i][f][e] = min(val[i][f][e], val[i + 1][x][e] + grp[i][f][x]);
                }
            }
        }
    }
    rep(i,mid + 1, rx + 1){
        rep(f,0,k){
            rep(e,0,k){
                val[i][f][e] = inf;
                rep(x,0,k){
                    val[i][f][e] = min(val[i][f][e], val[i - 1][f][x] + grp[i-1][x][e]);
                }
            }
        }
    }
    vector<Query> l, r;
    for(auto c: v){
        if(c.b.ff < mid){
            l.pb(c);
        }else if(c.a.ff > mid){
            r.pb(c);
        }else{
            ans[c.id] = inf;
            rep(i,0,k){
                ans[c.id] = min(ans[c.id], val[c.a.ff][c.a.ss][i] + val[c.b.ff][i][c.b.ss]);
            }
            if(ans[c.id] == inf) ans[c.id] = -1;
        }
    }
    slv(lx, mid - 1, l), slv(mid + 1, rx, r);
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n, m, q; cin >> k >> n >> m >> q;
    rep(i,0,n){
        rep(j,0,k){
            rep(t,0,k){
                grp[i][j][t] = inf;
            }
        }
    }
    rep(i,0,m){
        int u, v, w; cin >> u >> v >> w;
        grp[u/k][u%k][v%k] = w;
    }
    vector<Query> qs;
    rep(i,0,q){
        int u, v; cin >> u >> v;
        Query qq;
        qq.a = {u/k, u%k}, qq.b = {v/k, v%k};
        qq.id = i;
        qs.pb(qq);
    }
    // for(auto c: qs) cout << c.a.ff << ' ' << c.a.ss << ' ' << c.b.ff << ' ' << c.b.ss << '\n'; cout << endl;
    slv(0, n/k, qs);
    rep(i,0,q) cout << ans[i] << '\n';
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44