Submission #1285140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285140		kaysan	Toll (BOI17_toll)	C++20	100 / 100	104 ms	43508 KiB

toll

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pp pop_back
#define pf push_front
#define pt pop_front
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll>
#define pii pair<int,int>
#define vl vector<ll>
#define endl "\n"
#define fr(i,a,b) for(ll i=a; i<=b; i++)
#define fre(i,a,b) for(ll i=a; i>=b; i--)
#define kpnyh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// __builtin_ctzll(bits) kalo mau iterasi bits 1 nya aja
const ll maxn = 50005, maxn2 = 1e7+7, modn2 = 1e9+7, modn = 998244353;
using namespace std;
ll mul(ll x, ll y) {return (x*y) % modn;}
ll add(ll x, ll y) {return(x+y) % modn;}
ll dec(ll x, ll y) {return(x-y+modn) % modn;}
ll binpow(ll x, ll y) {ll ret = 1;while (y) {if (y&1) ret = mul(ret,x); y/=2;x = mul(x,x);}return ret;}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

//inget kalo dapet ide tulis dulu langkah langkahnya biar ngga ada yang ke skip
//lu pernah debug sampe tengah malem buat ide yang udah bener cuman gegara ada yang ke skip
 
ll te,n,m,k,q;

vector<vector<vector<ll>>>st,mtx;

void build(ll l, ll r, ll idx) {
	if (l == r) {
		for (ll i=0; i<k; i++) {
            for (ll j=0; j<k; j++) {
                st[idx][i][j] = mtx[l][i][j];
            }
        }
		return;
	}
	ll mid = (l + r) >> 1;
	build(l, mid, idx*2);
	build(mid+1, r, idx*2+1);
    ll lc = idx*2, rc = idx*2+1;
    // implemen floyd warshall ii sebagai perantara
    for (ll ii = 0; ii<k; ii++) {
        for (ll i=0; i<k; i++) {
            if  (st[lc][i][ii] == 1e18) continue;
            for (ll j=0; j<k; j++) {
                if (st[rc][ii][j] == 1e18) continue;
                st[idx][i][j] = min(st[idx][i][j], st[lc][i][ii] + st[rc][ii][j]);
            }
        }
    }
}

vector<vector<ll>>ans;

void qry(ll l, ll r, ll x, ll y, ll idx) {
	if (l > y || r < x) return;
	if (l >= x && r <= y) {
        vector<vector<ll>>res(k,vector<ll>(k,1e18));
		for (ll ii = 0; ii<k; ii++) {
            for (ll i=0; i<k; i++) {
                if (ans[i][ii] == 1e18) continue;
                for (ll j=0; j<k; j++) {
                    if (st[idx][ii][j] == 1e18) continue;
                    res[i][j] = min(res[i][j], ans[i][ii] + st[idx][ii][j]);
                }
            }
        }
        ans = res;
		return;
	}
	ll mid = (l + r) >> 1;
	qry(l,mid,x,y,idx*2);
	qry(mid+1,r,x,y,idx*2+1);
}

void solve() {
	cin>>k>>n>>m>>q;
    ll sz = n/k;
    vector<vector<vector<ll>>>dummymtx(sz,vector<vector<ll>>(k,vector<ll>(k,1e18)));
    vector<vector<vector<ll>>>dummyst(4*sz,vector<vector<ll>>(k,vector<ll>(k,1e18)));
    st = dummyst; mtx = dummymtx;
    // matrix 0 berarti hubungin dari level 0 ke level 1
    // makanya cuman butuh sz - 1
    for (ll i=1; i<=m; i++) {
        ll u,v,w; cin>>u>>v>>w;
        if (n < k) continue;
        ll lv = u/k;
        ll lv2 = v/k;
        ll id = u%k;
        ll id2 = v%k;
        mtx[lv][id][id2] = w;
    }
    if (n >= k) build(0,sz-1,1);
    // identity matrix
    vector<vector<ll>>dummy(k,vector<ll>(k,1e18));
    for (ll i=0; i<k; i++) dummy[i][i] = 0;
    while (q--) {
        ll u,v; cin>>u>>v;
        ll lv = u/k;
        ll lv2 = v/k;
        if (lv2 <= lv) {
            cout<<-1<<endl;
            continue;
        }
        ll id = u%k;
        ll id2 = v%k;
        ans = dummy;
        qry(0,sz-1,lv,lv2-1,1);
        if (ans[id][id2] == 1e18) cout<<-1<<endl;
        else cout<<ans[id][id2]<<endl;
    }
}
 
/*\
1
5
6 6 6 6 6
*/
 
int main () {
	kpnyh
	te=1;
 //   freopen("input.txt", "r", stdin);
 //   freopen("output.txt", "w", stdout);	
 //   cin>>te;
    while (te--) {
    	//cout<<endl;
        solve();
    }
}

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