Submission #404010

#	Time	Username	Problem	Language	Result	Execution time	Memory
404010		CSQ31	Toll (BOI17_toll)	C++14	15 / 100	190 ms	38668 KiB

toll

#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>(100000,INF)),rg(5,vector<ll>(100000,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 / 7
• Subtask 2: 0 / 10
• Subtask 3: 8 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44