oj.uz

Submission #404009

# Submission time Handle Problem Language Result Execution time Memory
404009 2021-05-13T16:48:41 Z CSQ31 Toll (BOI17_toll) C++14
15 / 100
 226 ms 109392 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5;
vector<vector<PII>>adj(MAXN),tadj(MAXN);
vector<int>l(MAXN),r(MAXN);
vector<ll>ans(MAXN,INF);
vii node(100000);
VII lf(5,vector<ll>(1000000,INF)),rg(5,vector<ll>(1000000,INF));
int n,k,m,o;
void re(int L,int R,vector<int>v){
	if(L == R){
		for(int x:v)ans[x] = -1;
		return;
	}
	int m = (L+R)/2;//compute rg
	for(int i=0;i<k;i++){
		lf[i][node[m][i]] = 0;
		rg[i][node[m][i]] = 0;
		for(PII x:adj[node[m][i]])rg[i][x.fi] = min(rg[i][x.fi],x.se);
		for(int j=m+1;j<=R;j++){
			for(int v:node[j]){	
				for(PII x:adj[v]){
					rg[i][x.fi] = min(rg[i][x.fi],rg[i][v]+x.se);
				}
			}
		}
		for(PII x:tadj[node[m][i]])lf[i][x.fi] = min(lf[i][x.fi],x.se);
		for(int j=m-1;j>=L;j--){
			for(int v:node[j]){	
				for(PII x:tadj[v]){
					lf[i][x.fi] = min(lf[i][x.fi],lf[i][v]+x.se);
				}
			}
		}		
	}
	vector<int>v0,v1;
	for(int x:v){
		if(l[x]/k <=m && r[x]/k>m){
			for(int i=0;i<k;i++)ans[x] = min(ans[x],lf[i][l[x]] + rg[i][r[x]]);
		}else if(l[x]/k > m)v1.pb(x);
		else if(r[x]/k <= m)v0.pb(x);
		
	}
	for(int i=0;i<k;i++){
		for(int j=L*k;j<(R+1)*k;j++)rg[i][j] = lf[i][j] = INF;
	}
	re(L,m,v0);
	re(m+1,R,v1);
}
int main()
{
	owo
	cin>>k>>n>>m>>o;
	for(int i=0;i<n;i++)node[i/k].pb(i);
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		adj[a].pb({b,c});
		tadj[b].pb({a,c});
	}
	for(int i=0;i<o;i++)cin>>l[i]>>r[i];
	vector<int>v;
	for(int i=0;i<n;i++)v.pb(i);
	re(0,(n-1)/k,v);
	for(int i=0;i<o;i++){
		if(ans[i] == INF)ans[i] = -1;
		cout<<ans[i]<<'\n';
	}
	
	
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 105000 KB Output is correct
2 Correct 50 ms 101232 KB Output is correct
3 Correct 49 ms 101256 KB Output is correct
4 Correct 51 ms 101200 KB Output is correct
5 Correct 50 ms 101176 KB Output is correct
6 Correct 51 ms 101256 KB Output is correct
7 Correct 51 ms 101168 KB Output is correct
8 Correct 109 ms 104864 KB Output is correct
9 Correct 102 ms 104752 KB Output is correct
10 Correct 70 ms 102628 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 106228 KB Output is correct
2 Correct 49 ms 101180 KB Output is correct
3 Correct 50 ms 101280 KB Output is correct
4 Correct 50 ms 101252 KB Output is correct
5 Correct 49 ms 101216 KB Output is correct
6 Correct 50 ms 101292 KB Output is correct
7 Incorrect 51 ms 101308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 101272 KB Output is correct
2 Correct 52 ms 101196 KB Output is correct
3 Correct 55 ms 101236 KB Output is correct
4 Correct 49 ms 101180 KB Output is correct
5 Correct 49 ms 101256 KB Output is correct
6 Correct 53 ms 101428 KB Output is correct
7 Correct 52 ms 101236 KB Output is correct
8 Correct 53 ms 101172 KB Output is correct
9 Correct 52 ms 101180 KB Output is correct
10 Correct 108 ms 105756 KB Output is correct
11 Correct 161 ms 106980 KB Output is correct
12 Correct 217 ms 108452 KB Output is correct
13 Correct 226 ms 109392 KB Output is correct
14 Correct 184 ms 107548 KB Output is correct
15 Correct 154 ms 101668 KB Output is correct
16 Correct 149 ms 101796 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 101272 KB Output is correct
2 Correct 52 ms 101196 KB Output is correct
3 Correct 55 ms 101236 KB Output is correct
4 Correct 49 ms 101180 KB Output is correct
5 Correct 49 ms 101256 KB Output is correct
6 Correct 53 ms 101428 KB Output is correct
7 Correct 52 ms 101236 KB Output is correct
8 Correct 53 ms 101172 KB Output is correct
9 Correct 52 ms 101180 KB Output is correct
10 Correct 108 ms 105756 KB Output is correct
11 Correct 161 ms 106980 KB Output is correct
12 Correct 217 ms 108452 KB Output is correct
13 Correct 226 ms 109392 KB Output is correct
14 Correct 184 ms 107548 KB Output is correct
15 Correct 154 ms 101668 KB Output is correct
16 Correct 149 ms 101796 KB Output is correct
17 Correct 164 ms 106660 KB Output is correct
18 Correct 49 ms 101276 KB Output is correct
19 Correct 49 ms 101264 KB Output is correct
20 Correct 52 ms 101308 KB Output is correct
21 Correct 50 ms 101260 KB Output is correct
22 Correct 50 ms 101172 KB Output is correct
23 Incorrect 51 ms 101176 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 105000 KB Output is correct
2 Correct 50 ms 101232 KB Output is correct
3 Correct 49 ms 101256 KB Output is correct
4 Correct 51 ms 101200 KB Output is correct
5 Correct 50 ms 101176 KB Output is correct
6 Correct 51 ms 101256 KB Output is correct
7 Correct 51 ms 101168 KB Output is correct
8 Correct 109 ms 104864 KB Output is correct
9 Correct 102 ms 104752 KB Output is correct
10 Correct 70 ms 102628 KB Output is correct
11 Correct 160 ms 106228 KB Output is correct
12 Correct 49 ms 101180 KB Output is correct
13 Correct 50 ms 101280 KB Output is correct
14 Correct 50 ms 101252 KB Output is correct
15 Correct 49 ms 101216 KB Output is correct
16 Correct 50 ms 101292 KB Output is correct
17 Incorrect 51 ms 101308 KB Output isn't correct
18 Halted 0 ms 0 KB -