제출 #361884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361884		ogibogi2004	Toll (BOI17_toll)	C++14	100 / 100	221 ms	35440 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5e4+6;
const ll INF=1e15;
const ll logN=18;
const ll MAXK=6;
struct query
{
	ll lb,rb,lk,rk;
	ll pos;
};
ll ans[2*MAXN],n,m,k;
ll prefL[MAXN][MAXK][MAXK];
ll prefR[MAXN][MAXK][MAXK];
ll matrix1[MAXN][MAXK];
ll matrix2[MAXN][MAXK];
void dq(ll l,ll r,vector<query>q)
{
	if(q.size()==0)return;
	ll mid=(l+r)/2;
	for(ll i1=0;i1<k;i1++)
	{
		for(ll i2=0;i2<k;i2++)
		{
			prefR[mid][i1][i2]=INF;
			prefL[mid][i1][i2]=INF;
		}
	}
	for(ll i=0;i<k;i++)
	{
		prefR[mid][i][i]=0;
		prefL[mid][i][i]=0;
	}
	for(ll j=mid+1;j<=r;j++)
	{
		for(ll k1=0;k1<k;k1++)
		{
			for(ll k2=0;k2<k;k2++)
			{
				prefR[j][k1][k2]=INF;
			}
		}
		for(ll k1=0;k1<k;k1++)
		{
			for(ll k2=0;k2<k;k2++)
			{
				for(ll k3=0;k3<k;k3++)
				{
					prefR[j][k1][k2]=min(prefR[j][k1][k2],prefR[j-1][k1][k3]+matrix1[(j-1)*k+k3][k2]);
				}
			}
		}
	}
	for(ll j=mid-1;j>=l;j--)
	{
		for(ll k1=0;k1<k;k1++)
		{
			for(ll k2=0;k2<k;k2++)
			{
				prefL[j][k1][k2]=INF;
			}
		}
		for(ll k1=0;k1<k;k1++)
		{
			for(ll k2=0;k2<k;k2++)
			{
				for(ll k3=0;k3<k;k3++)
				{
					prefL[j][k1][k2]=min(prefL[j][k1][k2],prefL[j+1][k1][k3]+matrix2[(j+1)*k+k3][k2]);
				}
			}
		}
	}
	vector<query>for_left,for_right;
	for(auto xd:q)
	{
		if(xd.rb<mid)
		{
			for_left.push_back(xd);
			continue;
		}
		if(xd.lb>mid)
		{
			for_right.push_back(xd);
			continue;
		}
		//cout<<mid<<" "<<l<<" "<<r<<endl;
		//cout<<xd.pos<<" "<<xd.lb*k+xd.lk<<" "<<xd.rb*k+xd.rk<<" :\n";
		ans[xd.pos]=INF;
		for(ll k1=0;k1<k;k1++)
		{
			//cout<<k1<<" "<<prefL[xd.lb][k1][xd.lk]<<" "<<prefR[xd.rb][k1][xd.rk]<<endl;
			ans[xd.pos]=min(ans[xd.pos],prefL[xd.lb][k1][xd.lk]+prefR[xd.rb][k1][xd.rk]);
		}
	}
	dq(l,mid-1,for_left);
	dq(mid+1,r,for_right);
}
int main()
{
	for(ll i=0;i<MAXN;i++)
	{
		for(ll j1=0;j1<MAXK;j1++)
		{
			matrix1[i][j1]=INF;
			matrix2[i][j1]=INF;
		}
	}
	cin>>k>>n>>m;
	ll o;cin>>o;
	
	for(ll i=1;i<=m;i++)
	{
		ll x,y,z;
		cin>>x>>y>>z;
		matrix1[x][y%k]=z;
		matrix2[y][x%k]=z;
	}
	vector<query>queries;
	for(ll i=0;i<o;i++)
	{
		ll x,y;
		cin>>x>>y;
		queries.push_back({x/k,y/k,x%k,y%k,i});
	}
	dq(0,n/k+1,queries);
	for(ll i=0;i<o;i++)
	{
		if(ans[i]>=INF)cout<<-1<<endl;
		else cout<<ans[i]<<endl;
	}
return 0;
}

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