Submission #361883

#	Time	Username	Problem	Language	Result	Execution time	Memory
361883		ogibogi2004	Toll (BOI17_toll)	C++14	0 / 100	121 ms	18216 KiB

toll

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+6;
const int INF=1e7;
const int logN=18;
const int MAXK=6;
struct query
{
	int lb,rb,lk,rk;
	int pos;
};
int ans[2*MAXN],n,m,k;
int prefL[MAXN][MAXK][MAXK];
int prefR[MAXN][MAXK][MAXK];
int matrix1[MAXN][MAXK];
int matrix2[MAXN][MAXK];
void dq(int l,int r,vector<query>q)
{
	if(q.size()==0)return;
	int mid=(l+r)/2;
	for(int i1=0;i1<k;i1++)
	{
		for(int i2=0;i2<k;i2++)
		{
			prefR[mid][i1][i2]=INF;
			prefL[mid][i1][i2]=INF;
		}
	}
	for(int i=0;i<k;i++)
	{
		prefR[mid][i][i]=0;
		prefL[mid][i][i]=0;
	}
	for(int j=mid+1;j<=r;j++)
	{
		for(int k1=0;k1<k;k1++)
		{
			for(int k2=0;k2<k;k2++)
			{
				prefR[j][k1][k2]=INF;
			}
		}
		for(int k1=0;k1<k;k1++)
		{
			for(int k2=0;k2<k;k2++)
			{
				for(int 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(int j=mid-1;j>=l;j--)
	{
		for(int k1=0;k1<k;k1++)
		{
			for(int k2=0;k2<k;k2++)
			{
				prefL[j][k1][k2]=INF;
			}
		}
		for(int k1=0;k1<k;k1++)
		{
			for(int k2=0;k2<k;k2++)
			{
				for(int 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(int 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(int i=0;i<MAXN;i++)
	{
		for(int j1=0;j1<MAXK;j1++)
		{
			matrix1[i][j1]=INF;
			matrix2[i][j1]=INF;
		}
	}
	cin>>k>>n>>m;
	int o;cin>>o;
	
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		matrix1[x][y%k]=z;
		matrix2[y][x%k]=z;
	}
	vector<query>queries;
	for(int i=0;i<o;i++)
	{
		int x,y;
		cin>>x>>y;
		queries.push_back({x/k,y/k,x%k,y%k,i});
	}
	dq(0,n/k+1,queries);
	for(int i=0;i<o;i++)
	{
		if(ans[i]>=INF)cout<<-1<<endl;
		else cout<<ans[i]<<endl;
	}
return 0;
}

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