oj.uz

Submission #878299

# Submission time Handle Problem Language Result Execution time Memory
878299 2023-11-24T08:06:14 Z manizare Toll (BOI17_toll) C++14
0 / 100
 3000 ms 23868 KB 
#include <bits/stdc++.h>
 
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define int long long
#define sz(v) (int)v.size()
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e4 + 10 , inf = 1e18 , mod = 998244353 ;
int k , n , m , q;
int  dis[maxn][5] , d[maxn] , mark[maxn] ;
vector <pii> G[maxn] ;
struct node{
	int s[5][5]  ,l , r;  
};
vector <int> his ; 
void dij(int v){
	priority_queue <pii> pq ;
	pq.push({0 , v}) ;
	d[v] = 0;
	while(pq.size()){
		int v = pq.top().S ; pq.pop() ;
		if(mark[v] == 1)continue ;
		his.pb(v);
		mark[v] = 1;
		for(pii u : G[v]){
			if(d[u.F] > d[v]+u.S){
				d[u.F] = d[v] + u.S ;
				pq.push({-d[u.F] , u.F}) ;
			}
		}
	}
}
void cle(){
	for(int v : his){
		d[v] = inf ; 
		mark[v] =0 ; 
	}
}

node seg[4*maxn]  ;
node operator+(node a,node b){
	node res ; 
	int l =a.l , r = b.r, mid = a.r ; 
	res.l = l ;
	res.r = r ;
	for(int i = 0 ;i  < k  ;i++){
		for(int j =0 ; j < k ; j++){
			G[l*k+i].pb({mid*k+j , a.s[i][j]}) ; 
			G[mid*k+i].pb({(mid+1)*k+j , dis[mid*k+i][j]});
			G[(mid+1)*k+i].pb({r*k+j , b.s[i][j]}); 
		}
	}
	for(int i =0 ; i < 5 ; i++){
		dij(l*k+i) ;
		for(int j =0 ; j < 5 ;j ++){
			res.s[i][j] = d[r*k+j] ;
		}
		cle();
	}
	for(int i =0  ; i < k ; i++){
		G[l*k+i].clear();
		G[mid*k+i].clear() ;
		G[(mid+1)*k].clear() ;
	} 
	return res ;
}

void bui(int p = 1 , int l = 0 , int r = n/k){
	int pl = p<<1 , pr = p << 1 | 1 , mid = (l+r)/2 ;
	for(int i =0 ; i < k ; i++){
		for(int j =0 ; j < k ; j++){
			seg[p].s[i][j] = inf ; 
		}
	}
	if(l == r){
		seg[p].l = l , seg[p].r=  r ;
		for(int i  =0 ;i < k ; i++){
			seg[p].s[i][i] = 0 ;
		}
		return ;
	}
	bui(pl , l, mid) ;
	bui(pr, mid+1,r);
	seg[p] = seg[pl] + seg[pr] ;
}
node que(int le ,int ri , int p = 1,int l = 0 , int r = n/k){
	int pl = p<<1 , pr = p << 1 | 1 , mid = (l+r)/2 ;
	if(le <= l && r <= ri){
		return seg[p] ;
	}
	if(mid >= ri){
		return que(le,ri,pl,l,mid);
	}
	if(mid < le){
		return que(le , ri ,pr,mid+1,r);
	}
	return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}

signed main() {
    ios :: sync_with_stdio(0); cin.tie(0);
	cin >> k >> n >> m >> q ;
	for(int i =0 ; i <= n; i++){
		for(int j =0 ; j < k ; j++){
			dis[i][j] = inf ; 
		}
	}
	for(int i = 1; i <= m; i++){
		int v , u , c;
		cin >> v >> u >> c ;
		dis[v][u%k] = min(dis[v][u%k] , c) ;
	}
	for(int i =0 ; i <= n+k; i++){
		d[i] = inf ;
	}
	bui();
	while(q--){
		int v ,u  ;
		cin >> v >> u ;
		if(v/k >= u/k){
			cout << -1 << "\n";
			continue ;
		}
		int ans= (que(v/k , u/k)).s[v%k][u%k];
		if(ans == inf){
			cout << -1 << "\n";
		}else{
			cout << ans << "\n";
		}
	}
}
/* 
 
 
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 23868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3101 ms 20424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4572 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 40 ms 7180 KB Output is correct
7 Correct 64 ms 7216 KB Output is correct
8 Correct 76 ms 5408 KB Output is correct
9 Correct 98 ms 5376 KB Output is correct
10 Execution timed out 3089 ms 23840 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4572 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 40 ms 7180 KB Output is correct
7 Correct 64 ms 7216 KB Output is correct
8 Correct 76 ms 5408 KB Output is correct
9 Correct 98 ms 5376 KB Output is correct
10 Execution timed out 3089 ms 23840 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 23868 KB Time limit exceeded
2 Halted 0 ms 0 KB -